2026/07/28 by Alexander Schmidhuber, Matthew B. Hastings
#math.CO #cs.DM #quant-ph
A nonempty subfamily of a k-uniform hypergraph is an 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 C nk/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.