A Spectral Proof of the Hypergraph Moore Bound

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\ge 3$ and every $1\le \mathrm{\ell }\le n$, any $k$-uniform hypergraph on $n$ vertices with more than $C{n}^{k\mathrm{/}2}\mathrm{/}{\mathrm{\ell }}^{k\mathrm{/}2-1}$ hyperedges contains an even cover of size at most $A\mathrm{\ell }\log (en\mathrm{/}\mathrm{\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.