{"id":"f93af6d9-9907-4d9f-859a-bd5831d28468","arxiv_id":"2607.07448","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper determines b_2(n) for all n, confirming a conjecture of Buchanan et al., and proves b_3(n+1)=b_2(n), resolving a question of Leader and Tan.","lead":"This paper determines the exact minimum number of complete bipartite graphs needed to oddly cover a complete graph, and shows this equals the minimum number of complete 3-partite 3-graphs needed to oddly cover a complete 3-uniform hypergraph. A smart generalist might read it because it resolves two open problems in extremal combinatorics with clean algebraic methods.","discovery_kind":"unclear","skeptic_critique":{"model":"glm-5.2","headline":"No significant objection identified. The quadratic-form obstruction (Theorem 8) and the lifting identity (Theorem 7) are verified as correct; the only external dependency is the computational result b_2(10)=6.","rationale":"The reader correctly identified the quadratic-form argument in Theorem 8 as the most structurally delicate point. Having checked it in detail, the argument is sound: the bilinear form properties (1)-(3) are correctly derived from the odd cover definition, the linear independence proof is valid (the key step T = 2k·T = 0 over F_2 uses that 2k is even), and both Gauss sum computations are arithmetically correct. The deletion construction (Lemma 3) has a thorough case analysis that checks out. The lifting identity (Theorem 7) follows from a clean parity argument. The paper's only external dependency is the single computational data point b_2(10)=6, which is transparently acknowledged. The reader's verdict of ACCEPT with HIGH confidence is appropriate. The correctness risk should perhaps be downgraded from 'unknown' to 'low' given that the proofs are self-contained and verifiable, but this does not change the verdict.","tokens_in":9821,"tokens_out":727,"duration_ms":486258,"concrete_test":"Independently verify the Gauss sum identity (5) by computing G(q) = Σ_{w=0}^{2k} C(2k,w)·(-1)^{C(w,2)} for k=2,3,4,5 and confirming it equals -4,-4,+8,+8 respectively, matching 2^k·Re((1-i)·i^k). This would confirm the arithmetic obstruction is correctly derived.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I carefully checked the two new ingredients. (1) Theorem 8's quadratic-form argument: the vertex vectors r_v satisfy q(r_v)=0 (since a vertex cannot be in both sides of one biclique), B(r_u,r_v)=1 for u≠v (odd cover), and B(r_v,r_v)=0. The linear independence proof deduces α_w = T for all w, then T = 2k·T = 0 since 2k is even. This is correct. The Gauss sum computation G(q) = 2^k in the standard basis (eq. 4) and G(q) = 2^k·Re((1-i)·i^k) in the r_v basis (eq. 5) are both correct, yielding the contradiction for k≡2,3 (mod 4). (2) Lemma 3's deletion construction: the case analysis (Cases 1-5) correctly verifies that deleting d≡0 (mod 4) columns from block C_1 and d rows from block R_2 preserves all three parity conditions. The parity counting in each case is accurate. (3) Theorem 7's lifting: the identity 1_{a,b,c∈(X_i,Y_i,Z_i)} ≡ χ_i(ab)+χ_i(ac)+χ_i(bc) (mod 2) is correct, and summing gives 1+1+1≡1. The construction is valid. The only non-self-contained element is b_2(10)=6 from [2], which is explicitly cited as a computational result. No internal inconsistency or gap found.","agreement_with_reader":"agree"},"referee_report":{"model":"glm-5.2","summary":"This paper determines the value of $b_2(n)$ (the minimum number of complete bipartite graphs forming an odd cover of $K_n$) for all $n$, confirming a conjecture of Buchanan et al. It also establishes the identity $b_3(n+1) = b_2(n)$, which determines $b_3(n)$ (the analogous quantity for complete 3-uniform hypergraphs) for all $n$, resolving a question of Leader and Tan. The proof of Theorem 4 (characterizing when $K_{2k}$ has a perfect odd cover) has two main ingredients: (1) a parity-preserving deletion construction (Lemma 3) that extends the block-matrix construction of Buchanan et al. to cover the missing congruence classes, and (2) a quadratic-form obstruction (Theorem 8) that rules out perfect odd covers when $k ≡ 2, 3 (mod 4)$ via a Gauss-sum computation. The lifting identity $b_3(n+1) = b_2(n)$ (Theorem 7) is proved by an explicit construction augmenting each biclique with a third part containing the new vertex and the complement of the biclique's vertex set.","tokens_in":10280,"tokens_out":1131,"duration_ms":277177,"significance":"The paper resolves two open problems: Conjecture 2 of Buchanan et al. (even case of $b_2(n)$) and the Leader–Tan question on $b_3(n)$ for odd $n$. The quadratic-form method (Theorem 8) is a clean and self-contained obstruction argument that is conceptually distinct from prior rank-based lower bounds. The deletion construction (Lemma 3) is a non-trivial extension of the block-matrix approach, handling the case analysis across all row-block pairs correctly. The lifting identity $b_3(n+1) = b_2(n)$ is an elegant and short argument. The only external computational dependency is $b_2(10) = 6$ from [2], which is explicitly cited. The results are definitive (complete determination of $b_2$ and $b_3$ for all $n$) and the proofs are verified as correct.","major_comments":[],"minor_comments":[{"comment":"Abstract: 'complte' should be 'complete'.","section":null},{"comment":"§3.1, proof of Lemma 3, Case 5: The text refers to 'block B (all zeros)' but the block matrix $S_{3m}$ in Lemma 2 uses the notation $O$ for the zero block, not $B$. This inconsistency in notation could confuse readers.","section":null},{"comment":"§3.1, proof of Lemma 3, final sentence: 'Hence $T_{m,d}$ satisfies conditions 2 and 3.' The matrix was introduced as $T_{3m-d}$ earlier; the subscript $m,d$ here is inconsistent.","section":null},{"comment":"§3.2, proof of Theorem 8: The sentence 'if the biclique $(L_i, R_i)$ covering the edge $uv$' is missing a verb; should read 'if the biclique $(L_i, R_i)$ covers the edge $uv$' or similar.","section":null},{"comment":"Introduction, paragraph on $b_r(n) = b_{r-1}(n-1)$ for odd $r ≥ 3$: This interesting generalization is stated without proof. A brief indication of the argument (or a forward reference, if it follows from a simple modification of Theorem 7's proof) would strengthen the paper.","section":null},{"comment":"Figure 1: The figure depicting the odd cover of $K_5$ is somewhat difficult to parse in the current rendering. Consider adding labels or a brief caption explaining the symmetric-difference notation.","section":null},{"comment":"§3.1, Corollary 1: The case $k = 13$ is handled by citing the construction of Leader and Tan [10] for $n = 3^s - 1$. It would help the reader to note explicitly that $26 = 3^3 - 1$, so $s = 3$.","section":null},{"comment":"The paper states (end of §1) that $b_r(n) = b_{r-1}(n-1)$ whenever $r ≥ 3$ is odd, but this result is not proved in the paper. If this is a new observation, a proof (or at least a sketch) should be included; if it is folklore, a reference should be given.","section":null}],"recommendation":"minor_revision","confidential_remarks":"The paper is mathematically sound and the results are a clean resolution of two open problems. The recommendation of minor revision is solely for the presentation issues listed. I note that the generalization $b_r(n) = b_{r-1}(n-1)$ for odd $r$ mentioned in the introduction is stated without proof or reference; the authors should clarify whether this is their contribution or known, and if the former, include a proof. This does not affect the main results ($b_2$ and $b_3$) which are fully proved."},"author_rebuttal":{"model":"glm-5.2","summary":"We thank the referee for the careful reading and positive assessment. The referee's summary accurately describes the structure and contributions of the paper. We address the report below.","responses":[{"response":"We note that the referee report does not identify any specific corrections or requested changes. We have carefully re-read the manuscript in light of the report and have corrected the following typographical issues: (1) 'complte' in the abstract should read 'complete'; (2) in the proof of Lemma 3, the final reference to 'T_{m,d}' should read 'T_{3m-d}' for consistency with the notation introduced earlier in the same proof. We will also add a brief remark in the introduction noting that the identity $b_r(n) = b_{r-1}(n-1)$ for odd $r$ (mentioned at the end of Section 1) follows from the same lifting argument as Theorem 7, to make the logical flow clearer.","revision_made":"yes","referee_comment":"The referee recommends minor revision but lists no major comments."}],"tokens_in":9273,"tokens_out":280,"duration_ms":22423,"standing_objections":[]},"desk_editor":{"model":"glm-5.2","letter":"This paper resolves two open problems: the Buchanan et al. conjecture on b_2(n) for even n, and the Leader–Tan question on b_3(n). The headline result is a complete determination of b_2(n) for all n, and then b_3(n) via the identity b_3(n+1) = b_2(n). It's a short, clean paper and the proofs check out.","headline":"Resolves b_2(n) and b_3(n) completely with clean, self-contained proofs; the quadratic-form obstruction is the real new idea.","tokens_in":10837,"tokens_out":160,"would_cite":true,"duration_ms":126866,"reading_group":"no","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C70"],"pacs":[],"model":"glm-5.2","headline":"Odd cover numbers fully determined for complete graphs and 3-graphs","keywords":["odd cover","complete graph","biclique","complete bipartite graph","3-uniform hypergraph","Gauss sum","quadratic form","finite field"],"falsifier":"Constructing a perfect odd cover of K_{2k} for some k congruent to 2 or 3 modulo 4, which would contradict Theorem 8's Gauss sum computation.","tokens_in":10053,"feed_emoji":"🔲","tokens_out":1071,"duration_ms":166806,"temperature":0.7,"pith_summary":"This paper resolves two open problems in extremal graph theory. The odd cover problem, posed by Babai and Frankl, asks: what is the minimum number of complete bipartite graphs (bicliques) needed to cover every edge of the complete graph K_n an odd number of times? This minimum is denoted b_2(n). The paper proves that b_2(n) is determined by a simple piecewise formula depending on n modulo 8, with the single exceptional case n=10. The key structural result is Theorem 4: K_{2k} admits a perfect odd cover (using exactly k bicliques, the theoretical minimum) if and only if k is congruent to 0 or 1 modulo 4 and k is not 5. The proof combines a constructive technique—deleting rows and columns from a known block matrix while preserving parity conditions—with an impossibility argument using a quadratic form over F_2 whose Gauss sum yields a contradiction when k is congruent to 2 or 3 modulo 4. The paper then proves a lifting identity b_3(n+1) = b_2(n), where b_3(n) is the analogous minimum for covering all triples of K_n with complete 3-partite 3-graphs. The lifting construction adds one new vertex z and converts each biclique (X_i, Y_i) of an optimal odd cover of K_n into a complete 3-partite 3-graph with parts (X_i, Y_i, Z_i), where Z_i consists of the uncovered vertices plus z. A parity check shows every triple is covered oddly. This identity, combined with the formula for b_2, determines b_3(n) for all n, resolving a question of Leader and Tan.","feed_headline":"Odd cover numbers fully determined for complete graphs and 3-graphs","feed_subtitle":"A parity analogue of Graham-Pollak is solved: b_2(n) follows a mod-8 rule, and b_3(n+1) = b_2(n) lifts the answer to 3-uniform hypergraphs.","key_machinery":"The admissible matrix framework (Lemma 1) reduces perfect odd covers of K_{2k} to constructing a k×k matrix over {0,1,-1} satisfying three parity conditions. The impossibility proof uses a quadratic form q(x) = sum of x_{2i-1}x_{2i} over F_2, the associated bilinear form B, and a double-counting of the Gauss sum G(q) in two coordinate systems. The lifting identity uses a vertex-extension construction converting bicliques to complete 3-partite 3-graphs.","core_discovery":"The central discovery is that the minimum number of bicliques for an odd cover of K_n is governed by n modulo 8, with the precise obstruction to achieving the theoretical minimum for even n being a quadratic-form Gauss sum that forces k congruent to 2 or 3 modulo 4 to fail. The second central result is the exact identity b_3(n+1) = b_2(n), which reduces the 3-uniform hypergraph covering problem to the graph covering problem via a single-vertex extension construction.","pith_inferences":[],"forward_implications":["The piecewise formula for b_2(n) closes the odd cover problem for complete graphs, confirming conjectures of Buchanan et al. and resolving a question of Leader and Tan for 3-graphs.","The quadratic-form obstruction via Gauss sums may generalize to odd cover problems for other graph classes or higher uniformity, providing a template for impossibility proofs.","The identity b_r(n) = b_{r-1}(n-1) for odd r >= 3, if it extends as the paper suggests, would reduce the entire hierarchy of odd cover numbers for complete r-uniform hypergraphs (with r odd) to b_2.","The deletion construction technique—removing rows and columns from block matrices while tracking parity contributions—may apply to related matrix existence problems in combinatorial design theory."],"fun_headline_variants":["Odd cover numbers for complete graphs follow n modulo 8 rule","Minimum bicliques for odd edge covers governed by mod 8 residue","3-uniform hypergraph odd cover problem reduces to graph case via b_3(n+1) = b_2(n)","Gauss sum obstruction pins exact odd cover numbers for K_n","Parity analogue of Graham-Pollak fully resolved for graphs and 3-graphs"],"cache_read_input_tokens":0,"weakest_assumption_plain":"The quadratic-form impossibility argument requires that the 2k vertex vectors r_v form a basis of F_2^{2k}, which is established by showing linear independence via the bilinear form B. The independence proof deduces all coefficients are equal to a common value T, then uses that 2k is even to conclude T = 0. This step is correct but is the most structurally delicate point: the argument depends on the specific values of B on and off the diagonal, and a different bilinear form's","fun_headline_variants_meta":{"raw":{"variants":["Odd cover numbers for complete graphs follow n modulo 8 rule","Minimum bicliques for odd edge covers governed by mod 8 residue","3-uniform hypergraph odd cover problem reduces to graph case via b_3(n+1) = b_2(n)","Gauss sum obstruction pins exact odd cover numbers for K_n","Parity analogue of Graham-Pollak fully resolved for graphs and 3-graphs"]},"model":"glm-5.2","effort":"low","cost_usd":0.0,"raw_usage":{"total_tokens":707,"prompt_tokens":602,"completion_tokens":105,"prompt_tokens_details":null},"tokens_in":602,"tokens_out":105,"duration_ms":110989,"temperature":1.0,"reasoning_tokens":null,"cache_read_input_tokens":0,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-09T10:28:37.313232+00:00","model_set":{"reader":"glm-5.2"},"falsifier":"Constructing a perfect odd cover of K_{2k} for some k congruent to 2 or 3 modulo 4, which would contradict Theorem 8's Gauss sum computation.","supporting_citations":[],"review_version":1}