{"id":"252e06fa-24fa-4f0d-9905-1c0cc5996ab8","arxiv_id":"2607.14068","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Every k-uniform hypergraph meeting Feige's density bound contains an even cover of size O(ρ log n), resolving the hypergraph Moore bound conjecture exactly.","lead":"This paper proves Feige's 2008 hypergraph Moore bound conjecture: a k-uniform hypergraph with enough edges must contain a small even cover, whose size is O(ρ log n). The proof removes the extra logarithmic factors left by all prior work, using a polynomial-counting argument on Kikuchi graphs.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Odd-k proof has unaddressed residue-overlap gap: Lemma 3.2's cross-edge claim can fail, so Δ=1 in Lemma 2.5 is unjustified.","rationale":"The even-k portion (Lemmas 2.1–2.4, Proposition 2.3, and the palette embedding) is self-contained and appears internally sound. The central claim for odd k, however, depends on Lemma 3.2 and the colored Kikuchi construction. The most load-bearing concern is not just that [HKM23] arguments are imported, but that the specific graph definition in §3.4 can fail to produce valid neighboring vertices when bucket residues overlap. Lemma 3.2's proof needs the cross-edge existence to force d_E(S)≥2; without it, the per-bucket degree bound Δ=1 is unsupported. Since Lemma 2.5's average-degree bound scales with Δ, the entire odd-k expansion argument collapses if Δ>1. This is a precise instance of the gap the reader already identified, so the verdict remains CONDITIONAL: the paper should supply the missing disjointness condition or a corrected proof of Lemma 3.2 before the odd-k result is considered verified.","tokens_in":12675,"tokens_out":35675,"duration_ms":275035,"concrete_test":"Construct the k=5, i=1 example described above as an actual hypergraph satisfying the §3.2 decomposition properties (with B_k large enough that τ_2>4). Verify that S is a valid ℓ-subset, that (E,F) and (E',F') are valid edges of Kc with signature (2,2), and that no valid T exists for (E,F') because v appears in both T(1) and T(2). If this construction succeeds, Lemma 3.2's proof step is invalid. Alternatively, check the original [HKM23] definition and decomposition to see whether an unstated disjointness condition on \\tilde E,\\tilde F is present; if so, the current paper must state it explicitly before the odd-k proof can be accepted.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In §3.4, Kc is defined on ℓ-subsets of [n]×{1,2}. For a label (E,F), T is determined by T(1)=S(1)∆\\tilde E and T(2)=S(2)∆\\tilde F. For T to lie in V(Kc), T(1) and T(2) must be disjoint. The definition does not require, and the text never proves, that \\tilde E∩\\tilde F=∅ for E,F in the same bucket. For small centers (§3.2, i≤(k−1)/2), property (3) permits τ_{i+1}>2, so two hyperedges in one bucket can share U_j and an extra vertex—hence overlapping residues. In the proof of Lemma 3.2, after finding two incident edges (E,F) and (E',F') with the same allowed signature, the text asserts S is incident to the cross edge (E,F'). Only the cardinality condition is checked. If \\tilde E∩\\tilde F' contains v outside S(1)∪S(2), toggling puts v in both T(1) and T(2), so no valid T exists. This is not a remote pathology: with k=5, i=1, residues \\tilde E={v,w,a,b}, \\tilde F={w,c,d,e}, \\tilde E'={x,y,z,p}, \\tilde F'={v,q,r,s}, and S(1)={w,a,x,y}, S(2)={c,d,q,r}, both (E,F) and (E',F') are valid with signature (2,2), but the cross edge (E,F') would put v in both copies. Consequently the claim that each bucket contributes at most one incident edge at every vertex of Kc** is not established, and Lemma 2.5 is applied with Δ=1 without support. The odd-k theorem therefore rests on an unverified assertion.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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].","tokens_in":13155,"tokens_out":16574,"duration_ms":150827,"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":[{"comment":"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","section":"§3.5, Lemma 3.2"},{"comment":"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.","section":"§3.5, §3.1"}],"minor_comments":[{"comment":"Typo: 'A direct analogue of Lemma 2.3' should presumably be 'Lemma 2.4' (the dense-core lemma for the even case).","section":"§3.5"},{"comment":"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.","section":"§3.5"},{"comment":"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.","section":"§3.4"},{"comment":"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.","section":"§3.6"}],"recommendation":"major_revision","confidential_remarks":"The even-k part is, in my reading, sound and would be a significant contribution by itself. The odd-k part is not yet in a publishable state: Lemma 3.2's proof has a genuine gap, and the authors explicitly defer several load-bearing steps to 'routine arguments'. I would recommend asking for a complete proof of the pruning/matching lemma, or a modified construction that provably yields Δ=1 in Lemma 2.5, before accepting the all-k claim. If such a proof cannot be supplied, the paper should be revised to claim only the even case."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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 Ẽ 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.\n\nI 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.\n\nWho 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.","headline":"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.","tokens_in":13622,"tokens_out":4523,"would_cite":true,"duration_ms":43266,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C65","05C35"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["hypergraph Moore bound","even cover","Kikuchi graph","polynomial method","hypergraph girth","Feige conjecture","LDPC codes"],"falsifier":"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.","tokens_in":12623,"feed_emoji":"📐","tokens_out":8838,"duration_ms":71460,"temperature":0.7,"pith_summary":"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.","feed_headline":"Hypergraph Moore bound conjecture proven for all k≥3","feed_subtitle":"Dense k-uniform hypergraphs must contain small even covers, with no extra log factor—tightening the LDPC code tradeoff.","key_machinery":"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","core_discovery":"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).","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["Hypergraph Moore bound proven with no log factors","All k≥3: Feige's even cover conjecture solved","Simple proof settles hypergraph Moore conjecture","Even covers tight: hypergraph Moore bound proven","No polylog: hypergraph Moore conjecture falls"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Hypergraph Moore bound proven with no log factors","All k≥3: Feige's even cover conjecture solved","Simple proof settles hypergraph Moore conjecture","Even covers tight: hypergraph Moore bound proven","No polylog: hypergraph Moore conjecture falls"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000431,"raw_usage":{"total_tokens":2050,"prompt_tokens":774,"completion_tokens":1276,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":518,"completion_tokens_details":{"reasoning_tokens":1203}},"tokens_in":518,"tokens_out":1276,"duration_ms":8886,"temperature":1.0,"reasoning_tokens":1203,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-02T02:52:37.519474+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}