The Hypergraph Moore Bound

Abstract

The hypergraph Moore bound conjectured by Feige (2008) controls the size of the smallest even cover in a $k$-uniform hypergraph in terms of the average density of hyperedges. An even cover is a set of hyperedges covering each vertex an even number of times, generalizing the notion of a cycle in a graph, so the size of the smallest non-trivial even cover provides a notion of hypergraph girth. Recent work, starting from the breakthrough result of Guruswami, Kothari, and Manohar (2022) proved the conjecture up to polylogarithmic factors, whose exponents were later gradually improved. We give a simple proof of Feige's original hypergraph Moore bound conjecture for all $k \geq 3$, with no superfluous polylogarithmic factors. For the case of $k$ even, our proof roughly follows the proof of the graph Moore bound, but works with colored walks in a Kikuchi graph built from a hypergraph and controls their growth using the polynomial method. The argument is then extended to the case of $k$ odd by adapting a procedure in [GKM22].

Disclosure

“d Use of AI. We would like to thank Benny Sudakov and Kevin Lucca for several insightful discussions on the topic of this paper, and Benny Sudakov in particular for valuable feedback on an earlier version of this manuscript. We used modern AI tools in this work, primarily GPT-5.6 Sol, but also GPT-5.5 Pro, Claude Opus 4.8, and Claude Fable 5. In fact, the core technical innovation in the proof was found by GPT-5.6 Sol. The authors were working on a program to attempt to establish ver”

PDF page 2

Classification

Substantial mathematical content or result generation

Multiplier

10

Verified

2026-08-23T18:55:32.989502Z

Structural counts