A Spectral Proof of the Hypergraph Moore Bound

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.

Disclosure

“this yields k-independent constants in Theorem 1.1 and also finds applications to other problems such as those in our companion paper [1]. On the use of AI models. All proof ideas were conceived and developed by the authors. We have used Large Language Models to assist with writing and proofreading. All mistakes are ours. 2 Even uniformity Throughout this section and the next, we choose the hierarchy level ℓ to lie in the central range 2k ≤ ℓ,”

PDF page 4

Classification

Proofreading, grammar, or spelling

Multiplier

1

Verified

2026-08-23T19:14:48.340737Z

Structural counts