combinatorics

A Spectral Proof of the Hypergraph Moore Bound

arXiv:2607.26028

summary

The paper proves Feige's hypergraph Moore bound conjecture, showing that any sufficiently dense k‑uniform hypergraph contains a small even cover, using new spectral bounds for Kikuchi matrices.

Abstract

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 \geq 3$ and every $1 \leq ℓ \leq n$ , any $k$ -uniform hypergraph on $n$ vertices with more than $C n^{k /2} / ℓ^{k /2 - 1}$ hyperedges contains an even cover of size at most $A ℓ lo g (e n / ℓ)$ . 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.

14 pages

Topics & keywords

#hypergraph theory #even cover #Moore bound #spectral methods #Kikuchi matriceshypergraph Moore boundeven coverKikuchi matrixspectral boundFeige conjecturek-uniform hypergraph