The Hypergraph Moore Bound

Afonso S. Bandeira; Dmitriy Kunisky; Lucas Pesenti; Petar Nizi\'c-Nikolac; Robert Wang

REVIEW 2 major objections 4 minor 2 cited by

This paper proves Feige's hypergraph Moore bound conjecture for every k ≥ 3: every sufficiently dense k-uniform hypergraph contains a small even cover, with no extra logarithmic factor.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-02 02:52 UTC pith:Y3GVPD43

load-bearing objection Even-k case is a clean, significant proof; the odd-k case has an unproven residue-overlap step, so the full conjecture is not yet established from this text. the 2 major comments →

arxiv 2607.14068 v2 pith:Y3GVPD43 submitted 2026-07-15 math.CO cs.DMcs.DS

The Hypergraph Moore Bound

Afonso S. Bandeira , Dmitriy Kunisky , Petar Nizi\'c-Nikolac , Lucas Pesenti , Robert Wang This is my paper

classification math.CO cs.DMcs.DS MSC 05C6505C35

keywords hypergraph Moore boundeven coverKikuchi graphpolynomial methodhypergraph girthFeige conjectureLDPC codes

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves Feige's hypergraph Moore bound conjecture for every uniformity k ≥ 3. Concretely, any k-uniform hypergraph on n vertices with m ≥ c_k n (n/ρ)^{k/2−1} edges must contain an even cover—a nonempty set of hyperedges covering every vertex an even number of times—of size at most C_k ρ log n. Prior proofs only reached this density up to polylogarithmic factors; here the bound holds at the conjectured scale. The even-uniform case carries the new ideas: a polynomial-method density bound on Kikuchi graphs gives the neighborhood growth that makes the classical Moore-bound argument work. The odd-uniform case follows by decomposing the hypergraph and applying the even argument to a colored Kikuchi graph. If correct, the result settles the conjecture and sharpens the associated LDPC code tradeoff.

Core claim

Feige's conjecture (Theorem 1.2) is established for all k ≥ 3. For even k, the proof shows that if the smallest even cover has size g, then every ball of radius g/2−1 in the level-ℓ Kikuchi graph has average degree at most 2ℓ (Lemma 2.1); combined with a dense-core minimum-degree bound of 32ℓ, balls grow by a factor of 16 at each step until the vertex budget of the Kikuchi graph is exhausted, forcing an even cover of size at most 4kρ log n (with c_k = 64 and C_k = 4k). The odd case is proved by partitioning hyperedges into buckets around small centers, pruning a colored Kikuchi graph into per-bucket matchings, and applying the same polynomial-method density bound (Lemma 3.3).

What carries the argument

The level-ℓ Kikuchi graph K_ℓ(H) has all ℓ-subsets of [n] as vertices and connects S,T when S△T is a hyperedge; edge colors are the hyperedges themselves. The load-bearing identity is the color-palette embedding: a ball of K_ℓ(H) maps into the Boolean hypercube (or a product of coordinate blocks) by recording, for each vertex, which hyperedge colors appear an odd number of times on a walk from the root, so adjacent Kikuchi vertices land at Hamming distance 1. The polynomial-method density bound (Lemma 2.5) then controls the average degree of such an embedded set: if its vertices can be separated by degree-≤d polynomials and each coordinate class of edges has maximum degree Δ, the induced gra

Load-bearing premise

For odd k, the proof depends on the unproven-in-detail assertion (Lemma 3.2 plus the 'routine arguments' in §3.5) that after the random σ-map and matching reduction, every vertex of the pruned colored Kikuchi graph is incident to at most one retained edge from each bucket, so that the polynomial density bound applies with Δ=1; if that fails for some bucket structure, the odd case is not established by this paper.

What would settle it

For even k, construct (or search for) a k-uniform hypergraph whose smallest even cover has size g but whose level-ℓ Kikuchi graph contains a ball of radius g/2−1 with average degree larger than 2ℓ; Lemma 2.1 would fail and the ball-growth argument would collapse. For odd k, exhibit a state S in the pruned colored Kikuchi graph that, after the σ-map and the 1/3 matching reduction, is incident to two retained edges from the same bucket with four distinct hyperedges; this directly contradicts Lemma 3.2's per-bucket degree-one claim and the Δ=1 application of Lemma 2.5.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

For even k, any k-uniform hypergraph with m ≥ 64 n (n/ρ)^{k/2−1} edges contains an even cover of size at most 4kρ log n.
For odd k, the same density scale guarantees an even cover of size O_k(ρ log n), eliminating the logarithmic overshoot left by previous proofs.
The linear-algebraic formulation transfers this to a rate–distance tradeoff for binary LDPC codes at the conjectured density.
The Moore-bound ball-growth argument now extends to hypergraphs without spending a polylog factor.
The even-case argument holds for all ρ in [1,n], covering the full density range from sparse to very dense hypergraphs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The polynomial-method density bound is a standalone combinatorial lemma; it likely transfers to other Kikuchi-type constructions (for example, locally decodable codes or tensor PCA) and could strip extra log factors from those settings too—this is an inference, not a claim of the paper.
The odd-case proof has a visible unfinished step: Lemma 3.2 ('routine arguments') is where a counterexample would appear. A reader wanting to convert this paper into a fully self-contained proof should make the σ-map and matching reduction explicit.
Since the constants were not optimized, the density threshold 64 n (n/ρ)^{k/2−1} is probably not tight; a sharpened version of the average-degree estimate in Proposition 2.3 is a natural target.
If the odd-case pruning can be simplified, the same two-step scheme (even core + bucket decomposition) may give a uniform treatment of all k, and possibly even recover the graph case k=2 as a limiting instance.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

Even-k case is a clean, significant proof; the odd-k case has an unproven residue-overlap step, so the full conjecture is not yet established from this text.

read the letter

The headline is the even-k proof. For even k, this paper gives the first exact proof of Feige's hypergraph Moore bound with no extra log factor, and it does so with a genuinely new polynomial-method ingredient. Lemma 2.2 — the density bound for subsets of the hypercube with delta functions of low degree — is elegant and the proof is a clean dimension count. The palette embedding into the hypercube is also nicely done; the observation that fixed-weight sets make inclusion into equality is exactly right. The ball-growing argument then goes through. I checked the main steps and found no hidden circularity or fitted constants. This part is solid and is a real advance over the GKM22–HKM25 line.

The odd-k case is where I have a real concern, and the stress-test note lands on something actual. In the proof of Lemma 3.2, after finding two incident edges (E,F) and (E',F') with the same intersection signature, the text asserts that S is incident to the cross edge (E,F'). That assertion is not justified. For (E,F') to be a valid edge, the toggled vertex set T must have T(1) and T(2) disjoint. This requires that the residues Ẽ and F̃' do not overlap outside S(1)∪S(2). Nothing in the proof establishes this, and it can fail — the stress-test example with k=5 and overlapping residues is concrete. The text only checks the cardinality condition. The paper explicitly says it did not reconstruct many HKM23 arguments, and the pruning step relies on those. So the claimed Δ=1 in Lemma 2.5 is unsupported for odd k. The odd-k theorem is therefore not established by this manuscript as written.

I want to be fair about proportion: the even-k theorem is significant on its own and deserves attention. The odd-k gap is in a section that is explicitly a sketch, but it is load-bearing for the full conjecture. This should be fixable — maybe by adding a disjointness condition or by a sharper counting argument — but the fix is not here.

Who gets value: combinatorists and coding theorists, and anyone using the Kikuchi method. The paper is clearly written and the even-k proof is worth studying. I would send it to a serious referee, with the expectation that the odd-k part needs real work. I would not cite the odd-k result as verified until the gap is closed.

Referee Report

2 major / 4 minor

Summary. The paper claims to prove Feige's hypergraph Moore bound conjecture for all k≥3. For even k, it shows that a k-uniform hypergraph on n vertices with m≥64n(n/ρ)^{k/2−1} edges contains an even cover of size at most 4kρ log n. The proof introduces a level-ℓ Kikuchi graph, proves a polynomial-method density bound on vertex subsets contained in a ball of radius below g/2−1 (Lemmas 2.2 and 2.5), embeds such balls into the hypercube via color palettes, and then uses a ball-growing argument. For odd k, the paper adapts the HKM decomposition into buckets and a colored Kikuchi graph; after a pruning and matching procedure (Lemma 3.2), it applies the same density bound and ball-growing argument. The even-k part is essentially self-contained; the odd-k part relies on several sketched adaptations of [HKM23].

Significance. Feige's hypergraph Moore bound is a central open problem with applications to LDPC codes, hypergraph girth, and CSP refutation; prior results left extra logarithmic factors. The even-k proof is an elegant, parameter-free derivation with explicit constants c_k=64 and C_k=4k, and its polynomial-method lemma and palette embedding are likely to be reusable. The odd-k extension is a natural adaptation of [HKM23], but as detailed below it is not yet rigorously established because a key pruning claim is unsupported. The absence of fitted parameters and the explicit constants are notable strengths.

major comments (2)

[§3.5, Lemma 3.2] The assertion 'As these are four distinct hyperedges, then S is incident to an edge (E,F′) in K_c' is load-bearing: it is used to contradict the pruning condition d_E(S)=1 and to conclude that each bucket contributes at most one edge at every vertex. The assertion is false as stated. For a fixed S, the candidate endpoint T for a label (E,F′) is forced: T^(1)=S^(1)∆\tilde E and T^(2)=S^(2)∆\tilde F′. For T to be a vertex of K_c, one needs T^(1)∩T^(2)=∅, which in particular requires \tilde E∩\tilde F′⊆S^(1)∪S^(2). The definition of K_c and the cardinality condition do not imply this. Concretely, for k=5, i=1, take \tilde E={v,w,a,b}, \tilde F={w,c,d,e}, \tilde E′={x,y,z,p}, \tilde F′={v,q,r,s}, S^(1)={w,a,x,y}, S^(2)={c,d,q,r}. Both (E,F) and (E′,F′) have the allowed signature (2,2), but for the cross label (E,F′) toggling puts v in both T^(1) and T^(2), so no valid T exists. Consequently
[§3.5, §3.1] The proof of Lemma 3.2 also leaves several load-bearing steps as 'routine': the existence of σ with 1/4 of the edges, the proof that each bucket contributes at most two edges at every state, the reduction by factor ≤3 to a matching, and the construction of the dense core are all asserted rather than proved. The manuscript explicitly says it did not reconstruct many arguments from [HKM23], but Lemma 3.2 is not a verbatim citation: it adapts the construction to a pruned and σ-restricted colored Kikuchi graph. The referenced claims in [HKM23] do not immediately cover these adaptations. Since the odd-case proof depends on these facts exactly where the adaptation matters, a complete proof or a precise formal reduction to specific results in [HKM23] is required.

minor comments (4)

[§3.5] Typo: 'A direct analogue of Lemma 2.3' should presumably be 'Lemma 2.4' (the dense-core lemma for the even case).
[§3.5] The sentence 'for every original hyperedge E, we retain only one of E^(1) and E^(2)' is unclear: E^(1) and E^(2) are not defined in the text. Presumably they refer to the two labeled copies of E in the colored Kikuchi graph; please define this notation.
[§3.4] The displayed condition on (|\tilde E∩S^(1)|, |\tilde F∩S^(2)|) is typeset in a garbled way; the two allowed pairs should be written explicitly with floor/ceil notation.
[§3.6] The final parameter choice for odd k is only 'pick c_k large enough' and 'C_k' is not given explicitly. The even-case theorem states explicit c_k=64, C_k=4k; the odd case should at least state that c_k,C_k are absolute constants depending only on k, and specify how large they must be relative to B_k and γ_k.

Circularity Check

0 steps flagged

No significant circularity: the derivation is self-contained or rests on independent prior lemmas, not on its own target.

full rationale

The even-uniform proof in Section 2 is self-contained: Lemma 2.1 is derived from the polynomial-method Lemma 2.2, whose proof is a dimension-counting argument independent of the target theorem. The palette embedding uses only the assumption that no even cover of size below g exists, and the polynomial f_S is constructed from the hypergraph rather than fitted to the conclusion. The ball-growing argument then derives the even cover bound without invoking Feige's conjecture. The odd-uniform proof in Section 3 does rely on external prior work, namely [HKM23, Algorithm 1], [HKM23, Claim 3.10] (Proposition 3.1), [HKM23, Lemma 3.4], and the GKM22 procedure. These are citations to other authors' independent results, not self-citations, and they do not assume the conjecture being proved; [HKM23] itself proved a weaker version with log factors, so using its structural lemmas is legitimate external support rather than circularity. The constants c_k and C_k are chosen after the inequalities are proved, not fitted to data or to the target statement, and no fitted parameter is renamed as a prediction. The manuscript does contain unproven 'routine arguments' in Lemma 3.2 and Section 3.5, and the paper itself notes in footnote 2 that many arguments from [HKM23] are not reconstructed; a reader may also worry about the residue-overlap gap in the sketch of Lemma 3.2. However, these are proof-completeness or correctness risks, not instances where the claimed result is equivalent to its inputs by construction. No step in the derivation reduces to Feige's conjecture, to a self-citation chain, or to a fitted parameter called a prediction.

Axiom & Free-Parameter Ledger

3 free parameters · 6 axioms · 0 invented entities

The proof introduces no data-fitted parameters and no new postulated entities. It depends on standard linear algebra, a standard average-degree core argument, and four external results from [HKM23] that are not proved in this paper; the odd-k case is therefore not fully self-contained.

free parameters (3)

c_k, C_k
Universal constants in Theorem 1.2; c_k=64, C_k=4k for even k, chosen sufficiently large for odd k. Hand-chosen, not fitted to data.
level ℓ = max{k/2, ⌈ρ⌉} (even), max{2k, ⌈ρ⌉} (odd)
Scale of the Kikuchi graph; a proof parameter chosen to make the average-degree lower bound (7) hold.
B_k, γ_k
Constants imported from [HKM23] for the odd case; existential, depend only on k, not computed.

axioms (6)

standard math Any n+1 vectors in F_2^n are linearly dependent.
Used in the large-ρ cases (Section 2.2, Section 3.1) to produce a small dependency.
standard math Every finite graph of average degree d contains a nonempty induced subgraph of minimum degree at least d/2.
Used in Lemma 2.4 and Lemma 3.2; one-line deletion proof given in footnote.
domain assumption [HKM23, Algorithm 1] partitions H into buckets satisfying properties (1)-(3) of Section 3.2.
Imported from prior work and not proved in this paper; load-bearing for odd k.
domain assumption [HKM23, Claim 3.10]: avg deg(K_c^⋆) ≥ γ_k m(ℓ/n)^(k/2) for a constant γ_k>0.
Used in Section 3.5 to find a dense core in the colored Kikuchi graph; not proved here.
domain assumption [HKM23, Lemma 3.4]: an even cover of size q in the derived even-uniform hypergraph Ĥ yields an even cover of size at most 2q in H.
Used in Section 3.3 to reduce large-center odd case to the even theorem.
standard math Ordinary Moore bound for graphs (k=2 case).
Used in Section 3.3 when the derived even-uniform hypergraph Ĥ is 2-uniform.

pith-pipeline@v1.3.0-alltime-deepseek · 12431 in / 26021 out tokens · 214142 ms · 2026-08-02T02:52:37.519474+00:00 · methodology

0 comments

read the original 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].

discussion (0)

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

The Kikuchi Hierarchy is Sharp for $k$XOR
cs.DS 2026-07 conditional novelty 8.0

Normalized Kikuchi matrices achieve the sharp m ~ rho^{-2} n^{k/2} / ell^{k/2-1} trade-off with no logarithmic loss for detection, recovery, and two-sided refutation in kXOR, with matching low-degree lower bounds.
A Spectral Proof of the Hypergraph Moore Bound
math.CO 2026-07 accept novelty 8.0

Proves Feige's conjecture: hypergraphs above the n^{k/2}/ℓ^{k/2−1} edge threshold always contain an even cover of size O(ℓ log(en/ℓ)).

Reference graph

Works this paper leans on

18 extracted references · cited by 2 Pith papers

[1]

Noga Alon and Shlomo Hoory and Nathan Linial , volume = 18, pages =
[2]

Small Linear Dependencies for Binary Vectors of Low Weight , author =
[3]

Parity check matrices and product representations of squares , journal =
[4]

Multilinear polynomials and

Alon, Noga and Babai, L. Multilinear polynomials and. Journal of Combinatorial Theory, Series A , volume=. 1991 , publisher=

1991
[5]

Warmuth , title =

David Haussler and Nick Littlestone and Manfred K. Warmuth , title =. Information and Computation , volume =
[6]

Warmuth , title =

David Haussler and Nick Littlestone and Manfred K. Warmuth , title =. Symposium on Foundations of Computer Science (FOCS) , pages =
[7]

Kothari and Peter Manohar , title =

Venkatesan Guruswami and Pravesh K. Kothari and Peter Manohar , title =. Proceedings of the Symposium on Theory of Computing (STOC) , pages =
[8]

Kothari and Sidhanth Mohanty , title =

Jun-Ting Hsieh and Pravesh K. Kothari and Sidhanth Mohanty , title =. Symposium on Discrete Algorithms (SODA) , pages =
[9]

International Mathematics Research Notices , volume =

Hsieh, Jun-Ting and Kothari,. International Mathematics Research Notices , volume =. 2025 , month =

2025
[10]

Symposium on Foundations of Computer Science (FOCS) , pages=

Feige, Uriel and Kim, Jeong Han and Ofek, Eran , title=. Symposium on Foundations of Computer Science (FOCS) , pages=
[11]

Kothari and Peter Manohar , title =

Omar Alrabiah and Venkatesan Guruswami and Pravesh K. Kothari and Peter Manohar , title =. Symposium on Theory of Computing (STOC) , pages =
[12]

Kothari and Peter Manohar , title =

Pravesh K. Kothari and Peter Manohar , title =. Symposium on Theory of Computing (STOC) , pages =
[13]

Kothari and Peter Manohar , title =

Pravesh K. Kothari and Peter Manohar , title =. Symposium on Foundations of Computer Science (FOCS) , pages =
[14]

Symposium on Foundations of Computer Science (FOCS) , pages =

Oliver Janzer and Peter Manohar , title =. Symposium on Foundations of Computer Science (FOCS) , pages =
[15]

Kothari and Andrew D

Arpon Basu and Jun-Ting Hsieh and Pravesh K. Kothari and Andrew D. Lin , title =. Symposium on Foundations of Computer Science (FOCS) , pages =
[16]

Wein and Ahmed

Alexander S. Wein and Ahmed. Symposium on Foundations of Computer Science (FOCS) , pages =
[17]

Kothari and Jeff Xu , title =

Pravesh K. Kothari and Jeff Xu , title =. Symposium on Discrete Algorithms (SODA) , pages =
[18]

and Cipolloni, Giorgio and Schr

Bandeira, Afonso S. and Cipolloni, Giorgio and Schr. Communications of the American Mathematical Society , volume =. 2026 , doi =

2026

[1] [1]

Noga Alon and Shlomo Hoory and Nathan Linial , volume = 18, pages =

[2] [2]

Small Linear Dependencies for Binary Vectors of Low Weight , author =

[3] [3]

Parity check matrices and product representations of squares , journal =

[4] [4]

Multilinear polynomials and

Alon, Noga and Babai, L. Multilinear polynomials and. Journal of Combinatorial Theory, Series A , volume=. 1991 , publisher=

1991

[5] [5]

Warmuth , title =

David Haussler and Nick Littlestone and Manfred K. Warmuth , title =. Information and Computation , volume =

[6] [6]

Warmuth , title =

David Haussler and Nick Littlestone and Manfred K. Warmuth , title =. Symposium on Foundations of Computer Science (FOCS) , pages =

[7] [7]

Kothari and Peter Manohar , title =

Venkatesan Guruswami and Pravesh K. Kothari and Peter Manohar , title =. Proceedings of the Symposium on Theory of Computing (STOC) , pages =

[8] [8]

Kothari and Sidhanth Mohanty , title =

Jun-Ting Hsieh and Pravesh K. Kothari and Sidhanth Mohanty , title =. Symposium on Discrete Algorithms (SODA) , pages =

[9] [9]

International Mathematics Research Notices , volume =

Hsieh, Jun-Ting and Kothari,. International Mathematics Research Notices , volume =. 2025 , month =

2025

[10] [10]

Symposium on Foundations of Computer Science (FOCS) , pages=

Feige, Uriel and Kim, Jeong Han and Ofek, Eran , title=. Symposium on Foundations of Computer Science (FOCS) , pages=

[11] [11]

Kothari and Peter Manohar , title =

Omar Alrabiah and Venkatesan Guruswami and Pravesh K. Kothari and Peter Manohar , title =. Symposium on Theory of Computing (STOC) , pages =

[12] [12]

Kothari and Peter Manohar , title =

Pravesh K. Kothari and Peter Manohar , title =. Symposium on Theory of Computing (STOC) , pages =

[13] [13]

Kothari and Peter Manohar , title =

Pravesh K. Kothari and Peter Manohar , title =. Symposium on Foundations of Computer Science (FOCS) , pages =

[14] [14]

Symposium on Foundations of Computer Science (FOCS) , pages =

Oliver Janzer and Peter Manohar , title =. Symposium on Foundations of Computer Science (FOCS) , pages =

[15] [15]

Kothari and Andrew D

Arpon Basu and Jun-Ting Hsieh and Pravesh K. Kothari and Andrew D. Lin , title =. Symposium on Foundations of Computer Science (FOCS) , pages =

[16] [16]

Wein and Ahmed

Alexander S. Wein and Ahmed. Symposium on Foundations of Computer Science (FOCS) , pages =

[17] [17]

Kothari and Jeff Xu , title =

Pravesh K. Kothari and Jeff Xu , title =. Symposium on Discrete Algorithms (SODA) , pages =

[18] [18]

and Cipolloni, Giorgio and Schr

Bandeira, Afonso S. and Cipolloni, Giorgio and Schr. Communications of the American Mathematical Society , volume =. 2026 , doi =

2026