1 Introduction↩︎

The classical Moore bound describes how large the girth of a graph can be given its average degree. In particular, Alon, Hoory, and Linial [1] proved that every graph on \(n\) vertices with average degree \(d> 2\) contains a cycle of length at most \(2\lceil \log_{d-1} n\rceil+2\). In this work, we study the analogous question for hypergraphs.

A natural analog of girth for a hypergraph is the size of its smallest even cover, where an even cover is a nonempty set of hyperedges such that every vertex belongs to an even number of hyperedges in that set. Feige [2] analyzed the size of the smallest even cover of random hypergraphs. Based on the intuition that random hypergraphs should be approximately extremal, he proposed the following generalization of the Moore bound.

There is an equivalent linear algebraic formulation of this conjecture. Represent each hyperedge \(E\subseteq [n]\) by its indicator vector \(\mathbf{1}_E\in \mathbb{F}_2^n\). Then, a set of hyperedges \(\{E_1, \ldots, E_q\}\) is an even cover precisely when \[\mathbf{1}_{E_1} + \cdots + \mathbf{1}_{E_q}=0\text{ in \mathbb{F}_2^n}\,. \label{eq:hyperedge-comb}\tag{1}\] Thus, Conjecture 1 postulates that, when ?? holds, any system of \(k\)-sparse linear equations over \(\mathbb{F}_2\) with \(n\) variables and \(m\) equations has a small non-trivial linear dependency. In coding theory, this translates into a bound on the rate-distance tradeoff of low-density parity-check (LDPC) error-correcting codes.

Our main result is a proof of Feige’s conjecture for \(k\)-uniform hypergraphs when \(k\) is even.

We have made no attempt to optimize the constants. The significance of Theorem 2 is that the density requirement in 2 is at the conjectured scale ?? , with no additional factor of \(\log n\).

1.1 Related Work↩︎

For even \(k\), Naor and Verstraëte [3] proved Feige’s conjecture in the high-density regime \(\rho = O(1)\) (meaning, for \(\rho\) constant independent of \(n\)). For even \(k\), this remained the only progress until the breakthrough work of Guruswami, Kothari, and Manohar [4], who obtained bounds throughout the full range of \(\rho\), but with an additional factor of \(\log^{4k+1} n\) in the density requirement ?? . This was improved to a single extra \(\log n\) factor independently by Munhá Correia and Sudakov [5] and by Hsieh, Kothari, and Mohanty [6]. Theorem 2 removes this logarithmic factor and thereby confirms Feige’s original conjecture for every even \(k\).

The case of odd \(k\) appears to be more difficult. For \(k=3\), [3] showed that \(m\ge C n^{1.5}\log n\) suffices to guarantee an even cover of size \(O(\log n)\), and [2] subsequently improved the density requirement to \(m\ge C n^{1.5}\sqrt{\log \log n}\). More recently, [7] proved that Feige’s conjecture holds for every odd \(k\) and \(\rho\le n/\log^2 n\), up to an additional factor of \(\log^{1/(k+1)} n\) in ?? . Among these prior works, the approach in [5], [7] is a purely combinatorial argument based on rainbow walks, and the closest in spirit to ours.

Several important problems in combinatorics and computer science admit natural formulations in terms of even covers in hypergraphs. Conjecture 1 was originally motivated by the existence of polynomial-time verifiable certificates of unsatisfiability for random constraint satisfaction problems at densities strictly below those at which known polynomial-time algorithms succeed in finding them [8]. As a consequence of their proof of Feige’s conjecture up to polylogarithmic factors, [4] showed the existence of such certificates in semirandom instances of constraint satisfaction problems.

To prove this result, [4] developed and popularized the “Kikuchi method” introduced in [9], which has since found numerous applications in average-case complexity [4], [10], [11] and coding theory [7], [12]–[16]. In particular, the strongest known results in most of these applications retain extra logarithmic factors analogous to the one that until now remained in the hypergraph Moore bound. The Kikuchi graphs underlying this method are also the starting point of our proof.

Acknowledgments and 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 versions of Conjecture 1 using random matrix theory (as in the line of work [4], [6]) and the analysis of certain limiting infinite-dimensional operators, leading to problems concerning lower bounds on numbers of combinatorial walks arising as tracial moments of these operators. A separate publication is forthcoming on other implications of this program. The argument found by GPT-5.6 Sol to establish the even-uniform hypergraph Moore bound was first given in a rather different language from how we have written it in this paper, but the crux of the argument was the same, using a diagonal polynomial system to bound the number of edges in a suitable subgraph of the hypercube.

The paper was written entirely by the authors. AI was used to scan the manuscript for typos and inconsistencies in notation. All errors are ours.

LP’s work on this project was supported by the Swiss National Science Foundation, grant no.. RW’s work on this project was supported by the Queen Elizabeth II Graduate Scholarship in Science and Technology (QEII-GSST).

2 Proof of Theorem 2↩︎

Throughout, let \(k\geq 4\) be even, let \(H\subseteq {\binom {[n]} k}\) be the edge set of a simple \(k\)-uniform hypergraph, and let \(m=\left|H\right|\).

We will often work over \(\mathbb{F}_2^H\), Boolean vectors indexed by (the hyperedges of) \(H\). For \(E\in H\), let \(\varepsilon_E\) be the corresponding standard basis vector (this is equivalently \(\mathbf{1}_{\{E\}}\) in the previous notation, but we reserve that notation exclusively for vectors in \(\mathbb{F}_2^n\) to avoid confusion).

We denote the natural logarithm by \(\log\). Given a positive integer \(n\) set \([n] \mathrel{\vcenter{:}}= \left\{1,2,\ldots, n\right\}\). All graphs discussed will be simple. For a graph \(G\), we write \(V(G)\) for its vertex set, \(\mathcal{E}(G)\) for its edge set (reserving the symbol \(E\) for hypergraph edges), and \(\mathcal{E}(A, B)\) for subsets \(A, B \subseteq V(G)\) for the set of edges with one endpoint in \(A\) and the other in \(B\) (in the latter notation, the graph \(G\) involved will be clear from context).

2.1 First Steps↩︎

Assume 2 holds. We first handle the easier case of \(\rho>n/(4k)\). Denote by the weight of a Boolean vector the number of entries equal to 1. Consider the vectors \(\mathbf{1}_E\) over \(E \in H\). Any non-trivial linear dependency between these vectors is precisely an even cover of \(H\) of that size, giving a solution to 1 . Each of these vectors has even weight \(k\), and thus lies in the subspace of \(\mathbb{F}_2^n\) of vectors of even weight, whose dimension is \(n - 1\). Using the crude bound \(m \geq 64n > n\), we conclude that any \(n\) of these vectors are linearly dependent. Hence, some nonempty collection of at most \(n\) distinct hyperedges is an even cover. As \(n<4k\rho<4k\rho\log n\), the result holds in this case.

From now on, we may therefore assume that \[\rho\leq \frac{n}{4k}. \label{eq:rho-asm}\tag{3}\] We argue by contradiction, and assume from here until we reach a contradiction at the end of the proof that \(H\) contains no even cover of size at most \(4k\rho\log n\).

2.2 The Kikuchi Graph and a Dense Subgraph↩︎

Set \[\ell \mathrel{\vcenter{:}}= \max\left\{\frac{k}{2},\lceil\rho\rceil\right\}. \label{eq:ell-choice}\tag{4}\] Since \(\lceil\rho\rceil\leq2\rho\leq(k/2)\rho\) and \(\rho\leq n/(4k)\), we have \[\rho\leq\ell\leq \frac{k\rho}{2} \leq\frac{n}{8},\] and so also \(\frac{k}{2}\leq \ell\leq n-\frac{k}{2}\), which will make the following construction well-defined.

We define the level-\(\ell\) Kikuchi graph \(K = K_\ell(H)\) to be the graph on \(\binom{[n]}{\ell}\) in which \(S, T \in \binom{[n]}{\ell}\) are adjacent if and only if \(S \Delta T \in H\). We further view the edge \(\{S, T\}\) as being colored by this \(S \Delta T\), so that \(K\) is edge-colored by the set \(H\). We denote the size of the vertex set of \(K\) by \[N \mathrel{\vcenter{:}}= \binom n\ell = |V(K)|.\]

For every \(E \in H\), the number of edges in \(K\) colored by \(E\) is the same, given by multiplying the number of ways to partition \(E\) into two equal parts of size \(k/2\) and the number of ways to choose a further subset of \([n]\) of size \(\ell - k/2\) disjoint from \(E\), divided by two. Using this in a double-counting calculation along with basic asymptotic estimates, we find the following.

The proof is given in Appendix 3.

Using this general calculation, we find that in our setting \(K\) must have a non-empty “core” dense subgraph of high minimum degree.

2.3 Outline of Remaining Argument↩︎

We now describe the general idea of the simple but somewhat subtle argument we give below. Recall the idea of the proof of the graph Moore bound (the case \(k = 2\)): an even cover in a graph is just a union of cycles, and the absence of short cycles means that a graph is locally tree-like, in which case its neighborhoods grow exponentially fast if the minimum degree is large. The absence of a cycle of length \(\Theta(\log n)\) then implies a contradiction since there are not enough vertices for these neighborhoods to continue growing exponentially without exhausting all vertices of the graph.

Our argument is similar, but working with the Kikuchi graph. As in the proof of the graph Moore bound, we pass to a subgraph \(K^\star\) with high enough minimum degree (in our case, \(K^\star\) is a subgraph of the Kikuchi graph). We cannot be so direct as to use the graph Moore bound on \(K^\star\), since the Kikuchi graph (and so \(K^\star\) as well) usually has short cycles, but ones that correspond only to trivial even covers. For example, suppose that \(k = \ell = 4\), and \(E_1 = \{1, 2, 3, 4\}\) and \(E_2 = \{5, 6, 7, 8\}\) both belong to \(H\). Then, \(\{1, 2, 5, 6\}, \{3, 4, 5, 6\}, \{3, 4, 7, 8\}, \{1, 2, 7, 8\}\) form a 4-cycle in \(K_{\ell}(H)\), but since the consecutive symmetric differences are \(E_1, E_2, E_1, E_2\), this cycle corresponds to a trivial even cover in \(H\).

Instead, we need to work only with the “interesting” cycles in \(K^\star\). To this end, call a cycle unpaired if some edge color in the cycle occurs an odd number of times, and define the unpaired girth of \(K^\star\), denoted \(\mathrm{oddgirth}(K^\star)\), as the minimal length of an unpaired cycle. By construction, there is an even cover in \(H\) of size at most \(\mathrm{oddgirth}(K^{\star})\) (consisting of the set of edge colors occurring an odd number of times in a shortest unpaired cycle). Thus, our assumption that there are no small even covers in \(H\) above implies that \(\mathrm{oddgirth}(K^\star) > 4k\rho\log n\).

Define \[q \mathrel{\vcenter{:}}= \lfloor 2k\rho \log n \rfloor < \frac{1}{2}\mathrm{oddgirth}(K^\star),\] which also satisfies, since \(\rho \geq 2\ell / k\), that \[q \geq \lfloor 4\ell \log n \rfloor \geq \lfloor 4 \log N \rfloor > \log_4 N > 1.\] Fix an arbitrary root \(S_0 \in V(K^\star)\). For \(0 \leq j \leq q - 1\), let \(\mathcal{N}_j\) be the ball of radius \(j\) centered at \(S_0\) in the graph distance of \(K^{\star}\). We then have \[\{S_0\} = \mathcal{N}_0 \subseteq \mathcal{N}_1 \subseteq \cdots \subseteq \mathcal{N}_{q - 1}.\] Our goal will be to conclude that, if there is no small even cover in \(H\), then these neighborhoods grow exponentially fast. Specifically, we will show that \(|\mathcal{N}_j| \geq 16 |\mathcal{N}_{j-1}|\) for each \(1 \leq j \leq q - 1\). Since \(q > \log_4 N\) while \(|V(K^\star)| \leq N\), this rate is too fast to persist all the way to radius \(q - 1\), and we will reach the desired contradiction.

To show that the neighborhoods grow exponentially fast, we use the following simple argument. First, by construction, the degree of each vertex in \(K^{\star}\) is at least \(32 \ell\). Since every edge with an endpoint in \(\mathcal{N}_j\) has to have another endpoint in \(\mathcal{N}_{j+1}\), we have that \(|\mathcal{E}(\mathcal{N}_{j+1}, \mathcal{N}_{j+1})|\geq |\mathcal{E}(\mathcal{N}_j, \mathcal{N}_{j+1})|\geq 16\ell |\mathcal{N}_j|\).

The crux of the argument is then to control the edge density in each neighborhood, where we will show \(\ell|\mathcal{N}_{j+1}|\geq |\mathcal{E}(\mathcal{N}_{j+1}, \mathcal{N}_{j+1})|\), yielding the exponential growth of neighborhoods. We now focus on this part of the argument.

2.4 Polynomial Interpolation↩︎

To give this upper bound on the number of internal edges, we use the following bound, whose proof is akin to that of Frankl-Wilson-type theorems in [17]. A similar result appears in the work of Haussler, Littlestone, and Warmuth [18], phrased in terms of the one-inclusion graph and the Vapnik-Chervonenkis (VC) dimension.

Below we write \(d_H\) for the Hamming distance on the hypercube.

We give a self-contained proof in Appendix 4.

The polynomials \((f_v)_{v\in V}\), which act as the standard basis of indicator functions when restricted to \(A:=\{p_v:v\in V\}\), are known as a diagonal polynomial system over \(A\). The conclusion of Lemma 2 can then be interpreted as bounding the expansion of a subgraph of the hypercube admitting a low-degree diagonal polynomial system.

We next describe the hypercube labeling that we will use to apply this result to \(\mathcal{N}_j\), associating with each \(S \in \mathcal{N}_j\) a Boolean vector. We call this the color palette of \(S\), denoted \(p_S = \mathrm{pal}(S) \in \mathbb{F}_2^H\), because it is associated with the sequence of colors (edges of \(H\)) encountered along a walk from \(S_0\) to \(S\).

Note also that the color palette \(\mathrm{pal}(S)\) together with the choice of root \(S_0\) determines \(S\), since from \(\mathrm{pal}(S)\) we may compute \(\mathbf{1}_{S_0} + \sum_{i = 1}^t (\mathbf{1}_{S_i} + \mathbf{1}_{S_{i-1}}) = \mathbf{1}_S\).

We observe that, if two \(S_1,S_2 \in \mathcal{N}_j\) are adjacent as vertices of \(K\), then their palettes must have Hamming distance 1. Thus the condition on the vertex labeling of Lemma 2 is satisfied if we take \(p_S \mathrel{\vcenter{:}}= \mathrm{pal}(S)\). It remains to produce a suitable collection of low-degree polynomials \(f_S\) for \(S \in \mathcal{N}_j\).

Consider the following polynomials: \[f_S(X) = \prod_{v \in S}\left(\mathbbold{1}\{v \in S_0\} + \sum_{E \in H: v \in E} X_E\right).\] To see why these polynomials satisfy the condition of Lemma 2, consider the evaluation with \(X = \mathrm{pal}(T)\). The expression \(\mathbbold{1}\{v \in S_0\} + \sum_{E \in H: v \in E} X_E\) counts the number of times vertex \(v\) is visited along a walk from \(S_0\) to \(T\), modulo 2, which, by the definition of a walk in the Kikuchi graph, is simply \(\mathbbold{1}\{v \in T\}\). Thus we have \[f_S(\mathrm{pal}(T)) = \prod_{v \in S} \mathbbold{1}\{v \in T\} = \mathbbold{1}\{S \subseteq T\} = \mathbbold{1}\{S = T\},\] the final step following because \(|S| = |T|\). We emphasize that this simple last step is a crucial consequence of working over the Kikuchi graph defined on sets of a fixed cardinality (equivalently, a slice of the hypercube of fixed weight \(\ell\)), and that on this slice inclusion of sets implies equality.

We also have \(\deg(f_S) \leq |S| = \ell\). Thus, applying Lemma 2 with this choice of polynomials \(f_S\), we arrive at: \[\label{eq:edgedensitybound-in-Nj} |\mathcal{E}(\mathcal{N}_j, \mathcal{N}_j)| \leq \ell |\mathcal{N}_j|,\tag{5}\] which holds for each \(1 \leq j \leq q - 1\).

2.5 Final Steps↩︎

We now put together the results established above to finish the proof, as outlined in Section 2.3 above.

3 Proof of Proposition 3↩︎

We first show ?? . For a given \(E \in H\), the number of pairs \((S, T) \in V(K)^2\) such that \(S \Delta T = E\) is \[\binom{k}{k/2}\binom{n - k}{\ell - k/2}.\] Thus, \[\sum_{S \in V(K)} \deg(S) = m\binom{k}{k/2}\binom{n - k}{\ell - k/2},\] and the formula for \(\mathop{\mathrm{avg\,deg}}(K)\) follows upon dividing by \(|V(K)| = \binom{n}{\ell}\).

We next show ?? . Define \(s \mathrel{\vcenter{:}}= k/2\). Then, ?? can be rewritten as \[\mathop{\mathrm{avg\,deg}}(K) = \binom{k}{s} \cdot m \cdot \frac{(\ell)_s(n - \ell)_s}{(n)_{2s}}, \label{eq:kikuchi95average95degree95falling}\tag{6}\] where \((a)_b = a(a - 1) \cdots (a - b + 1)\) is the falling factorial. Since \(\ell \geq s\) by assumption, we have the estimate \[(\ell)_s \geq \frac{s!}{s^s}\ell^s.\] Moreover, \(\ell\leq n/8\) and \(s\leq n/8\), so \[(n-\ell)_s \geq \left(\frac{3n}{4}\right)^s, \qquad\qquad (n)_{2s} \leq n^{2s}.\] Combining 6 with these estimates, we find that \[\mathop{\mathrm{avg\,deg}}(K) \geq \beta_s m\left(\frac{\ell}{n}\right)^s,\] where \[\beta_s = \binom{2s}{s}\frac{s!}{s^s}\left(\frac{3}{4}\right)^s.\] We claim that \(\beta_s>1\). Indeed, \[\beta_s = \left(\frac{3}{4}\right)^s \prod_{j=1}^s\left(1+\frac{j}{s}\right).\] Since \(x\mapsto\log(1+x)\) is increasing, \[\frac{1}{s}\sum_{j=1}^s\log\left(1+\frac{j}{s}\right) \geq \int_0^1\log(1+x)\,\mathrm dx =2\log 2-1.\] Therefore \[\log\beta_s \geq s\left(\log(3/4)+2\log 2-1\right) =s(\log 3-1)>0,\] completing the proof.

4 Proof of Lemma 2↩︎

Write \(A \mathrel{\vcenter{:}}= \{p_v: v \in V\} \subseteq \mathbb{F}_2^m\) for the subset of vertex labels. Write \(Q\) for the graph on vertex set \(\mathbb{F}_2^m\) where two vectors are connected if their Hamming distance is 1, the standard Boolean hypercube graph. Then \(A\) is a subset of vertices of \(Q\), and we write \(Q[A]\) for the subgraph induced on these vertices. We have \(|\mathcal{E}(G)| \leq |\mathcal{E}(Q[A])|\) by assumption that vertices have distinct labels, so it suffices to bound the latter quantity (note, however, that \(G\) is only isomorphic to a subgraph of \(Q[A]\), but the latter may have strictly more edges and the above inequality may be strict).

Recall that we assume there are polynomials \(f_v \in \mathbb{F}_2[X_1, \dots, X_m]\) of degree at most \(d\) whose restrictions to \(A\) give the indicator functions of each vertex of \(A\). In particular, the restrictions to \(A\) of the low-degree squarefree monomials \(X^I \mathrel{\vcenter{:}}= \prod_{j \in I} X_j\) over \(|I| \leq d\) span all functions \(\mathbb{F}_2^A\). Choose some collection \(\mathcal{B}\) of exactly \(|A|\) such monomials whose restrictions form a basis.

Recall that we write \(\varepsilon_i \in \mathbb{F}_2^m\) for the standard basis vectors for \(i \in [m]\). For each \(i \in [m]\), define \[\mathcal{E}_i(A) \mathrel{\vcenter{:}}= \left\{\{x,x+\varepsilon_i\}:x,x+\varepsilon_i\in A\right\}.\] The edges in \(\mathcal{E}_i(A)\) form a matching, these are disjoint sets of edges, and they partition \(\mathcal{E}(Q[A])\). Define the operator \[D_i:\mathbb{F}_2^A\longrightarrow\mathbb{F}_2^{\mathcal{E}_i(A)}, \qquad (D_if)(\{x,x+\varepsilon_i\}) =f(x)+f(x+\varepsilon_i).\] Because \(\mathcal{E}_i(A)\) is a matching, for any choice of Boolean values prescribed to each edge in \(\mathcal{E}_i(A)\), there exists an \(f\) such that \(D_i f\) takes those values. Hence, \[\operatorname{rank}D_i=\left|\mathcal{E}_i(A)\right|.\]

Now, let \(b_i\) be the number of monomials in the basis \(\mathcal{B}\) that include the variable \(X_i\), i.e., \[b_i \mathrel{\vcenter{:}}= \left|\left\{X^I\in\mathcal{B}:i\in I\right\}\right|.\] If \(i\notin I\), then \(X^I\) takes the same value at the two endpoints of every edge of \(\mathcal{E}_i(A)\), and therefore \(D_i\left(X^I|_A\right)=0\). Thus, \[\operatorname{rank}D_i \leq b_i.\] Summing over all \(i\) and combining these bounds, we find, \[|\mathcal{E}(G)| \leq \left|\mathcal{E}\left(Q[A]\right)\right| =\sum_{i=1}^m\left|\mathcal{E}_i(A)\right| \leq\sum_{i=1}^m b_i =\sum_{X^I\in\mathcal{B}}\left|I\right| \leq d\left|\mathcal{B}\right| =d\left|A\right|,\] completing the proof.

References↩︎