Let k≥ 3, and let a k-uniform hypergraph be a hypergraph in which every hyperedge contains exactly k vertices. An even cover is a nonempty set of hyperedges such that every vertex belongs to an even number of hyperedges in that set. For integers n≥ k and 1≤ rho≤ n, let m denote the number of hyperedges in a k-uniform hypergraph on n vertices. Feige's hypergraph Moore bound conjecture. For every k≥ 3, there exist constants c_k,C_k>0 such that, whenever m≥ c_k n(frac n rho)^frac k2-1, the hypergraph contains an even cover of size at most C_k rholog n. This conjecture is a hypergraph analogue of the Moore bound for graphs and is motivated by Feige's analysis of the smallest even cover in random hypergraphs. Its resolution status is not specified in the supplied source.

Feige’s hypergraph Moore-bound conjecture

About 18 years old · traced to 2008

Let $k\ge 3$ , and let a $k$ -uniform hypergraph be a hypergraph in which every hyperedge contains exactly $k$ vertices. An even cover is a nonempty set of hyperedges such that every vertex belongs to an even number of hyperedges in that set. For integers $n\ge k$ and $1\le \rho\le n$ , let $m$ denote the number of hyperedges in a $k$ -uniform hypergraph on $n$ vertices.

Feige's hypergraph Moore bound conjecture. For every $k\ge 3$ , there exist constants $c_k,C_k>0$ such that, whenever

m\ge c_k n\left(\frac n\rho\right)^{\frac k2-1},

the hypergraph contains an even cover of size at most $C_k\rho\log n$ .

This conjecture is a hypergraph analogue of the Moore bound for graphs and is motivated by Feige's analysis of the smallest even cover in random hypergraphs. Its resolution status is not specified in the supplied source.

Equivalent formulations 1Other wordings

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

Feige’s hypergraph Moore-bound conjecture
At the conjectured density, must every $k$ -uniform hypergraph contain a short nontrivial even cover, with constants free of superfluous polylogarithmic factors?

References

Primary source

Afonso S. Bandeira, Dmitriy Kunisky, Petar Nizić-Nikolac, Lucas Pesenti and Robert Wang, “The Hypergraph Moore Bound”, arXiv:2607.14068 (2026).

Posted 2 months ago

Progress summary

Refreshed 1 month ago

Claimed solved

A new preprint claims to remove the last extra logarithmic factor and settle the conjecture in all dimensions, but the proof has not yet been independently verified.

Feige posed the conjecture in 2008: at density $m\asymp n(n/\rho)^{k/2-1}$ , every $k$ -uniform hypergraph should contain an even cover of size $O(\rho\log n)$ .

Known results

Naor and Verstraëte (2008) proved the even- $k$ case for $\rho=O(1)$ .
Guruswami, Kothari, and Manohar (2022) handled all $\rho$ with an extra factor of $\log^{4k+1}n$ ; Munhá Correia–Sudakov (2022) and Hsieh–Kothari–Mohanty (2023) reduced this to one factor of $\log n$ .
For odd $k$ , Naor–Verstraëte and Feige obtained progressively better bounds; [HKM+25] reached general odd $k$ in a restricted range, still with a factor of $(\log n)^{1/(k+1)}$ .

July 2026 all- $k$ claim

The revised preprint claims that for every $k\geq3$ , $m\geq c_kn(n/\rho)^{k/2-1}$ guarantees an even cover of size at most $C_k\rho\log n$ , removing the extra polylogarithmic loss. For even $k$ , it gives $c_k=64$ and $C_k=4k$ . The paper credits the core technical innovation to GPT-5.6 Sol; the mathematical claim remains unverified.

Current status (as of July 2026): The preprint gives a complete claimed proof for every $k\geq3$ at the conjectured density scale; independent verification is still outstanding.

GPT-5.6 SolOpenAIsolved2026-07-01evidence

Sources

No solutions have been posted yet.