亚洲男人的天堂2018av,欧美草比,久久久久久免费视频精选,国色天香在线看免费,久久久久亚洲av成人片仓井空

In fair division of a connected graph $G = (V, E)$, each of $n$ agents receives a share of $G$'s vertex set $V$. These shares partition $V$, with each share required to induce a connected subgraph. Agents use their own valuation functions to determine the non-negative numerical values of the shares, which determine whether the allocation is fair in some specified sense. We introduce forbidden substructures called graph cutsets, which block divisions that are fair in the EF1 (envy-free up to one item) sense by cutting the graph into "too many pieces". Two parameters - gap and valence - determine blocked values of $n$. If $G$ guarantees connected EF1 allocations for $n$ agents with valuations that are CA (common and additive), then $G$ contains no elementary cutset of gap $k \ge 2$ and valence in the interval $\[n - k + 1, n - 1\]$. If $G$ guarantees connected EF1 allocations for $n$ agents with valuations in the broader CM (common and monotone) class, then $G$ contains no cutset of gap $k \ge 2$ and valence in the interval $\[n - k + 1, n - 1\]$. These results rule out the existence of connected EF1 allocations in a variety of situations. For some graphs $G$ we can, with help from some new positive results, pin down $G$'s spectrum - the list of exactly which values of $n$ do/do not guarantee connected EF1 allocations. Examples suggest a conjectured common spectral pattern for all graphs. Further, we show that it is NP-hard to determine whether a graph admits a cutset. We also provide an example of a (non-traceable) graph on eight vertices that has no cutsets of gap $\ge 2$ at all, yet fails to guarantee connected EF1 allocations for three agents with CA preferences.

Given a spanning tree $T$ of a planar graph $G$, the co-tree of $T$ is the spanning tree of the dual graph $G^*$ with edge set $(E(G)-E(T))^*$. Gr\"unbaum conjectured in 1970 that every planar 3-connected graph $G$ contains a spanning tree $T$ such that both $T$ and its co-tree have maximum degree at most 3. While Gr\"unbaum's conjecture remains open, Biedl proved that there is a spanning tree $T$ such that $T$ and its co-tree have maximum degree at most 5. By using new structural insights into Schnyder woods, we prove that there is a spanning tree $T$ such that $T$ and its co-tree have maximum degree at most 4.

Classical Krylov subspace projection methods for the solution of linear problem $Ax = b$ output an approximate solution $\widetilde{x}\simeq x$. Recently, it has been recognized that projection methods can be understood from a statistical perspective. These probabilistic projection methods return a distribution $p(\widetilde{x})$ in place of a point estimate $\widetilde{x}$. The resulting uncertainty, codified as a distribution, can, in theory, be meaningfully combined with other uncertainties, can be propagated through computational pipelines, and can be used in the framework of probabilistic decision theory. The problem we address is that the current probabilistic projection methods lead to the poorly calibrated posterior distribution. We improve the covariance matrix from previous works in a way that it does not contain such undesirable objects as $A^{-1}$ or $A^{-1}A^{-T}$, results in nontrivial uncertainty, and reproduces an arbitrary projection method as a mean of the posterior distribution. We also propose a variant that is numerically inexpensive in the case the uncertainty is calibrated a priori. Since it usually is not, we put forward a practical way to calibrate uncertainty that performs reasonably well, albeit at the expense of roughly doubling the numerical cost of the underlying projection method.

A graph $G=(V,E)$ is said to be distance magic if there is a bijection $f$ from a vertex set of $G$ to the first $|V(G)|$ natural numbers such that for each vertex $v$, its weight given by $\sum_{u \in N(v)}f(u)$ is constant, where $N(v)$ is an open neighborhood of a vertex $v$. In this paper, we introduce the concept of $p$-distance magic labeling and establish the necessary and sufficient condition for a graph to be distance magic. Additionally, we introduce necessary and sufficient conditions for a connected regular graph to exhibit distance magic properties in terms of the eigenvalues of its adjacency and Laplacian matrices. Furthermore, we study the spectra of distance magic graphs, focusing on singular distance magic graphs. Also, we show that the number of distance magic labelings of a graph is, at most, the size of its automorphism group.

We expound on some known lower bounds of the quadratic Wasserstein distance between random vectors in $\mathbb{R}^n$ with an emphasis on affine transformations that have been used in manifold learning of data in Wasserstein space. In particular, we give concrete lower bounds for rotated copies of random vectors in $\mathbb{R}^2$ by computing the Bures metric between the covariance matrices. We also derive upper bounds for compositions of affine maps which yield a fruitful variety of diffeomorphisms applied to an initial data measure. We apply these bounds to various distributions including those lying on a 1-dimensional manifold in $\mathbb{R}^2$ and illustrate the quality of the bounds. Finally, we give a framework for mimicking handwritten digit or alphabet datasets that can be applied in a manifold learning framework.

Let $X$ be a $d$-dimensional simplicial complex. A function $F\colon X(k)\to \{0,1\}^k$ is said to be a direct product function if there exists a function $f\colon X(1)\to \{0,1\}$ such that $F(\sigma) = (f(\sigma_1), \ldots, f(\sigma_k))$ for each $k$-face $\sigma$. In an effort to simplify components of the PCP theorem, Goldreich and Safra introduced the problem of direct product testing, which asks whether one can test if $F\colon X(k)\to \{0,1\}^k$ is correlated with a direct product function by querying $F$ on only $2$ inputs. Dinur and Kaufman conjectured that there exist bounded degree complexes with a direct product test in the small soundness regime. We resolve their conjecture by showing that for all $\delta>0$, there exists a family of high-dimensional expanders with degree $O_{\delta}(1)$ and a $2$-query direct product tester with soundness $\delta$. We use the characterization given by a subset of the authors and independently by Dikstein and Dinur, who showed that some form of non-Abelian coboundary expansion (which they called "Unique-Games coboundary expansion") is a necessary and sufficient condition for a complex to admit such direct product testers. Our main technical contribution is a general technique for showing coboundary expansion of complexes with coefficients in a non-Abelian group. This allows us to prove that the high dimensional expanders constructed by Chapman and Lubotzky satisfies the necessary conditions, thus admitting a 2-query direct product tester with small soundness.

We introduce $\varepsilon$-approximate versions of the notion of Euclidean vector bundle for $\varepsilon \geq 0$, which recover the classical notion of Euclidean vector bundle when $\varepsilon = 0$. In particular, we study \v{C}ech cochains with coefficients in the orthogonal group that satisfy an approximate cocycle condition. We show that $\varepsilon$-approximate vector bundles can be used to represent classical vector bundles when $\varepsilon > 0$ is sufficiently small. We also introduce distances between approximate vector bundles and use them to prove that sufficiently similar approximate vector bundles represent the same classical vector bundle. This gives a way of specifying vector bundles over finite simplicial complexes using a finite amount of data, and also allows for some tolerance to noise when working with vector bundles in an applied setting. As an example, we prove a reconstruction theorem for vector bundles from finite samples. We give algorithms for the effective computation of low-dimensional characteristic classes of vector bundles directly from discrete and approximate representations and illustrate the usage of these algorithms with computational examples.

Construction of a large class of Mutually Unbiased Bases (MUBs) for non-prime power composite dimensions ($d = k\times s$) is a long standing open problem, which leads to different construction methods for the class Approximate MUBs (AMUBs) by relaxing the criterion that the absolute value of the dot product between two vectors chosen from different bases should be $\leq \frac{\beta}{\sqrt{d}}$. In this chapter, we consider a more general class of AMUBs (ARMUBs, considering the real ones too), compared to our earlier work in [Cryptography and Communications, 14(3): 527--549, 2022]. We note that the quality of AMUBs (ARMUBs) constructed using RBD$(X,A)$ with $|X|= d$, critically depends on the parameters, $|s-k|$, $\mu$ (maximum number of elements common between any pair of blocks), and the set of block sizes. We present the construction of $\mathcal{O}(\sqrt{d})$ many $\beta$-AMUBs for composite $d$ when $|s-k|< \sqrt{d}$, using RBDs having block sizes approximately $\sqrt{d}$, such that $|\braket{\psi^l_i|\psi^m_j}| \leq \frac{\beta}{\sqrt{d}}$ where $\beta = 1 + \frac{|s-k|}{2\sqrt{d}}+ \mathcal{O}(d^{-1}) \leq 2$. Moreover, if real Hadamard matrix of order $k$ or $s$ exists, then one can construct at least $N(k)+1$ (or $N(s)+1$) many $\beta$-ARMUBs for dimension $d$, with $\beta \leq 2 - \frac{|s-k|}{2\sqrt{d}}+ \mathcal{O}(d^{-1})< 2$, where $N(w)$ is the number of MOLS$(w)$. This improves and generalizes some of our previous results for ARMUBs from two points, viz., the real cases are now extended to complex ones too. The earlier efforts use some existing RBDs, whereas here we consider new instances of RBDs that provide better results. Similar to the earlier cases, the AMUBs (ARMUBs) constructed using RBDs are in general very sparse, where the sparsity $(\epsilon)$ is $1 - \mathcal{O}(d^{-\frac{1}{2}})$.

Two graphs $G$ and $H$ are homomorphism indistinguishable over a class of graphs $\mathcal{F}$ if for all graphs $F \in \mathcal{F}$ the number of homomorphisms from $F$ to $G$ is equal to the number of homomorphisms from $F$ to $H$. Many natural equivalence relations comparing graphs such as (quantum) isomorphism, spectral, and logical equivalences can be characterised as homomorphism indistinguishability relations over certain graph classes. Abstracting from the wealth of such instances, we show in this paper that equivalences w.r.t. any self-complementarity logic admitting a characterisation as homomorphism indistinguishability relation can be characterised by homomorphism indistinguishability over a minor-closed graph class. Self-complementarity is a mild property satisfied by most well-studied logics. This result follows from a correspondence between closure properties of a graph class and preservation properties of its homomorphism indistinguishability relation. Furthermore, we classify all graph classes which are in a sense finite (essentially profinite) and satisfy the maximality condition of being homomorphism distinguishing closed, i.e. adding any graph to the class strictly refines its homomorphism indistinguishability relation. Thereby, we answer various questions raised by Roberson (2022) on general properties of the homomorphism distinguishing closure.

In 1973, Lemmens and Seidel posed the problem of determining the maximum number of equiangular lines in $\mathbb{R}^r$ with angle $\arccos(\alpha)$ and gave a partial answer in the regime $r \leq 1/\alpha^2 - 2$. At the other extreme where $r$ is at least exponential in $1/\alpha$, recent breakthroughs have led to an almost complete resolution of this problem. In this paper, we introduce a new method for obtaining upper bounds which unifies and improves upon previous approaches, thereby yielding bounds which bridge the gap between the aforementioned regimes and are best possible either exactly or up to a small multiplicative constant. Our approach relies on orthogonal projection of matrices with respect to the Frobenius inner product and as a byproduct, it yields the first extension of the Alon-Boppana theorem to dense graphs, with equality for strongly regular graphs corresponding to $\binom{r+1}{2}$ equiangular lines in $\mathbb{R}^r$. Applications of our method in the complex setting will be discussed as well.