A nonempty subfamily of a $k$-uniform hypergraph is an \emph{even cover} if every vertex lies in an even number of its hyperedges; for $k=2$ these are edge-disjoint unions of cycles, so the minimum size of an even cover is the natural hypergraph analogue of girth. We prove Feige's 2008 conjecture on the hypergraph Moore bound: there are absolute constants $A$ and $C$ (independent of $k$) such that for every $k\ge3$ and every $1\le\ell\le n$, any $k$-uniform hypergraph on $n$ vertices with more than $C\,n^{k/2}/\ell^{k/2-1}$ hyperedges contains an even cover of size at most $A\,\ell\log(en/\ell)$. Our proof is based on sharp spectral bounds for Kikuchi matrices, which we expect to be of independent interest; we apply them to the refutation of random constraint satisfaction problems in a companion paper.
A nonempty subfamily of a k-uniform hypergraph is an \emph{even cover} if every vertex lies in an even number of its hyperedges; for k=2 these are edge-disjoint unions of cycles, so the minimum size of an even cover is the natural hypergraph analogue of girth. We prove Feige's 2008 conjecture on the hypergraph Moore bound: there are absolute constants A and C (independent of k) such that for every k≥3 and every 1≤ℓ≤n, any k-uniform hypergraph on n vertices with more than Cnk/2/ℓk/2−1 hyperedges contains an even cover of size at most Aℓlog(en/ℓ). Our proof is based on sharp spectral bounds for Kikuchi matrices, which we expect to be of independent interest; we apply them to the refutation of random constraint satisfaction problems in a companion paper.
Motivated by the phenomenon of contextuality in quantum physics we study a particular family of proofs of the Kochen-Specker theorem.A proof is represented by a pair consisting of a hypergraph where each vertex has even degree, called an Eulerian hypergraph, and a labeling of its vertices.If a hypergraph admits a labeling constituting a proof, we say it is magic.We are interested in determining whether a given hypergraph is magic.Working with the duals of Eulerian hypergraphs, we develop the parity minor relation, which allows us to establish a concept of minimality for the magic property.We introduce a splitting operation to show that certain hypergraphs are not magic.We combine the parity minor relation and the splitting operation in order to search for minimally magic hypergraphs whose duals are grafts, hypergraphs with one edge of size four and all other edges of size two.
For a k-regular graph of odd order n we study the edge-ray scenario (contexts = vertices, rays = edges, uniform one-hot rows, each outcome bit flipped with probability η/2). A parity argument gives η*_F ≥ η_par = 1 − (1 − 2/n)^(1/k); we ask when it is tight. We prove tightness, even in the strong form (every S_k-symmetric row law on the parity slice), for locally set-transitive graphs containing all (a, b)-subgraphs, among them the odd graph K(7, 3) (for odd cycles this also follows from the complete set of n-cycle noncontextuality inequalities of Araújo et al.). For vertex-transitive graphs we reduce tightness to reachability of k/2 explicit staircase vertices of a weight polytope, show that the first one is reachable iff a balancing condition on perfect matchings holds, and prove this condition for every connected vertex-transitive graph of odd order; the proof uses the theorem of Zhang and Sun that such graphs of degree ≥ 4 are 3-factor-critical. Since the last staircase vertex is always reachable, tightness follows for every connected vertex-transitive graph of odd order and degree 4; for the middle staircase vertices we give a reduction to random regular spanning subgraphs with uniform rows and an odd-cut condition. Among the 406 connected vertex-transitive graphs of odd order n ≤ 21 we certify tightness exactly for 312, including all 287 of degree k ≤ 10; without vertex transitivity the bound can fail. An exact matching criterion shows that the strong form fails for 163 of the 406 graphs. For the edge scenario of K_n we prove η*_F = 1 − (2⌈n/2⌉ − 1)^(−1/2) for all n ≥ 2 (formalised in Lean), and show that the sufficient condition of our earlier paper (paper 6, 10.5281/zenodo.23481180) fails for n ≥ 6 and for the two-qubit doily, although equality holds there.
The encoding of 3-uniform edge-ordered weighted hypergraphs into multiqubit quantum states is proposed. We derive an analytical expression for the geometric measure of entanglement of hypergraph quantum states and establish its relation to hypergraph properties. The results establish a direct connection between the local structure of hypergraphs, hyperedge weights, and the entanglement of the corresponding quantum states. For equally weighted hypergraphs, it is shown that the entanglement depends explicitly on the vertex degree. The dependence of entanglement on hypergraph parameters is studied analytically and using quantum computing. Hypergraph states associated with chain, star, regular lattice, and binary-tree hypergraphs are examined, and their entanglement is quantified using quantum computing. These results open up the possibility of studying hypergraph properties with quantum programming.
Let H be a (non-empty) graph on n vertices, possibly containing isolated vertices. Let f_H(G) = 1 iff the input graph G on n vertices contains H as a (not necessarily induced) subgraph. Let alpha_H denote the cardinality of a maximum independent set of H. In this paper we show: Q(f_H) = Omega( sqrt{alpha_H * n}), where Q(f_H) denotes the quantum query complexity of f_H. As a consequence we obtain lower bounds for Q(f_H) in terms of several other parameters of H such as the average degree, minimum vertex cover, chromatic number, and the critical probability. We also use the above bound to show that Q(f_H) = Omega(n^{3/4}) for any H, improving on the previously best known bound of Omega(n^{2/3}) [M. Santha/A. Chi-Chih Yao, unpublished manuscript]. Until very recently, it was believed that the quantum query complexity is at least square root of the randomized one. Our Omega(n^{3/4}) bound for Q(f_H) matches the square root of the current best known bound for the randomized query complexity of f_H, which is Omega(n^{3/2}) due to Groger. Interestingly, the randomized bound of Omega(alpha_H * n) for f_H still remains open. We also study the Subgraph Homomorphism Problem, denoted by f_{[H]}, and show that Q(f_{[H]}) = Omega(n). Finally we extend our results to the 3-uniform hypergraphs. In particular, we show an Omega(n^{4/5}) bound for quantum query complexity of the Subgraph Isomorphism, improving on the previously known Omega(n^{3/4}) bound. For the Subgraph Homomorphism, we obtain an Omega(n^{3/2}) bound for the same.
We prove constant lower bounds for the spectral gap of the following random walks on unitary groups SU(2n) on n qubits. (i) Random Pauli Rotation: choose an n-qubit Pauli operator P and an angle θ∈[0,2π), both uniformly at random, and apply eiθP. (ii) Brickwork Random Unitary Circuit: choose n−1 unitaries Ui uniformly at random from SU(4) (including central phases of the parent group) independently, and apply U2j−1 on two qubits 2j−1,2j and then U2j on two qubits 2j,2j+1. Importantly, the gap bounds are independent of n and apply for all finite dimensional unitary representations of SU(2n) uniformly.
Our results immediately imply that the Random Pauli Rotation and Brickwork Random Unitary Circuit converge to approximate unitary t-designs after O(nt) steps. As a consequence, we improve implications for the complexity growth of random unitary circuits as a function of the depth. The existing argument can be applied almost verbatim, but previously the depth had to be O(2cn) for some c<1. Our unconditional constant spectral gap removes this restriction.
We prove analogous constant-gap results for orthogonal and Clifford groups; the latter is indispensable for our result on the Brickwork Random Unitary Circuit. The former implies convergence to approximate orthogonal t-designs. In this case, the implied mixing time with respect to a constant additive and multiplicative error is optimal (up to an absolute constant factor) for t=2.
Answering a question of Claudet, we prove that the uniformly random graph G∼G(n,1/2) is Ω(n)-vertex-minor universal with high probability. That is, for some constant α≈0.911, any graph on any αn specified vertices of G can be obtained as a vertex-minor of G. This has direct implications for quantum communications networks: an n-vertex k-vertex-minor universal graph corresponds to an n-qubit k-stabilizer universal graph state, which has the property that one can induce any stabilizer state on any k qubits using only local operations and classical communications.
We further employ our methods in two other contexts. We obtain a bipartite pivot-minor version of our main result, and we use it to derive a universality statement for minors in random binary matroids. We also introduce the vertex-minor Ramsey number Rvm(k) to be the smallest value n such that every n-vertex graph contains an independent set of size k as a vertex-minor. Supported by our main result, we conjecture that Rvm(k) is polynomial in k. We prove Ω(k2)≤Rvm(k)≤2k−1.