A Spectral Proof of the Hypergraph Moore Bound
2026-07-28 • Discrete Mathematics
Discrete Mathematics
AI summaryⓘ
The authors study a special collection of edges called an even cover in a uniform hypergraph, where each vertex appears in an even number of these edges. They extend a known graph concept (girth) to hypergraphs and prove a conjecture by Feige about how large such structures must be when the hypergraph is dense. Their main result provides explicit constants to bound the size of these even covers based on the number of vertices and edges. They use advanced techniques involving spectral analysis of Kikuchi matrices, which also have applications in solving other problems like random constraint satisfaction.
hypergraphk-uniform hypergrapheven covergirthMoore boundspectral boundsKikuchi matricesconstraint satisfaction problemsrandom CSPFeige's conjecture
Authors
Alexander Schmidhuber, Matthew B. Hastings
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\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.