The even-uniform hypergraph Moore bound
2026-07-15 • Discrete Mathematics
Discrete MathematicsData Structures and Algorithms
AI summaryⓘ
The authors provide a simpler and more precise proof of a mathematical conjecture by Feige about hypergraphs, which are like networks with edges connecting multiple points at once. This conjecture relates to finding the smallest group of edges that cover each point an even number of times, extending the idea of cycles in normal graphs. Previous work had only managed to prove this with some extra error factors, but the authors remove those factors entirely for all even-sized edges. Their approach adapts methods from graph theory using colored paths in a special graph associated with the hypergraph and uses polynomial interpolation to control complexity.
hypergraphMoore boundeven coverk-uniform hypergraphhypergraph girthcolored walksKikuchi graphpolynomial interpolationgraph theory
Authors
Afonso S. Bandeira, Dmitriy Kunisky, Petar Nizić-Nikolac, Lucas Pesenti, Robert Wang
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 even $k\ge 4$, with no superfluous polylogarithmic factors. 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 a polynomial interpolation method.