REVIEW 8 minor 11 references
Odd covers for complete graphs and complete 3-graphs
T0 review · 0 major / 8 minor · reviewed 2026-07-09 · glm-5.2
Pith's one-line read Odd cover numbers fully determined for complete graphs and 3-graphs
desk verdict Resolves b_2(n) and b_3(n) completely with clean, self-contained proofs; the quadratic-form obstruction is the real new idea. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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
Editorial extensions
If this is right
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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.
minor comments (8)
- Abstract: 'complte' should be 'complete'.
- §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.
- §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.
- §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.
- 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.
- 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.
- §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$.
- 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.
Simulated Author's Rebuttal
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.
read point-by-point responses
-
Referee: The referee recommends minor revision but lists no major comments.
Authors: 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: yes
Circularity Check
No significant circularity found.
full rationale
The paper's derivation chain is self-contained and genuine. Theorem 4 (perfect odd cover iff k≡0,1 mod 4, k≠5) is proved from two independent ingredients: (1) a constructive deletion method (Lemma 3, §3.1) that starts from the block matrix S_{3m} of Buchanan et al. [3] and verifies parity preservation by explicit case analysis, and (2) a quadratic-form obstruction (Theorem 8, §3.2) that computes a Gauss sum in two bases over F_2 to derive a contradiction for k≡2,3 mod 4. Neither ingredient is defined in terms of the target result. Theorem 7 (b_3(n+1)=b_2(n)) is proved by an explicit lifting construction: given an odd cover of K_n by bicliques (X_i,Y_i), a new vertex z is added with Z_i = (V(K_n)∖(X_i∪Y_i))∪{z}, and the parity identity 1_{a,b,c∈(X_i,Y_i,Z_i)} ≡ χ_i(ab)+χ_i(ac)+χ_i(bc) (mod 2) is verified directly. The only external dependencies are: the starting matrix S_{3m} from [3] (different author group), the computational result b_2(10)=6 from [2] (different author group), and the lower bound b_r(n)≥b_{r-1}(n-1) from Leader and Tan [10] (different authors). No result is defined in terms of the quantity it claims to derive. No self-citation chain is load-bearing. The quadratic-form argument is a first-principles F_2 computation with no fitted parameters.
Assumptions & free parameters
assumptions (4)
- standard math The 2k vertex vectors r_v in F_2^{2k} are linearly independent, hence form a basis.
- standard math The Gauss sum G(q) = Σ_{x∈F_2^{2k}} (-1)^{q(x)} is basis-independent.
- domain assumption b_2(10)=6, established by computer-aided calculation in Buchanan et al. [2].
- domain assumption The block matrix S_{3m} is admissible when m≡3 (mod 4).
Cite this review
Pith. "Pith review of Odd covers for complete graphs and complete 3-graphs." pith.science (2026). https://pith.science/paper/ZGJ5JOXU
@misc{pith2026260707448,
author = {Pith},
title = {Pith review of: Odd covers for complete graphs and complete 3-graphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/ZGJ5JOXU}},
note = {Machine review of arXiv:2607.07448}
}
abstract
The Graham-Pollak theorem says that one needs at least $n - 1$ complete bipartite graphs to cover each edge of a complete graph $K_{n}$ on $n$ vertices exactly once. The odd cover problem is a parity analogue which seeks the minimum number of complete bipartite graphs, denoted by $b_2(n)$, such that each edge of $ K_n $ is covered an odd number of times. An odd cover of a complte 3-graph $K_n^{(3)}$ on $n$ vertices is a family of complete $3$-partite $3$-graphs such that every triple is covered an odd number of times. Let $b_3(n)$ be the minimum size of such a family. The values of $b_2(n)$ and $b_3(n)$ are determined for some $n$ in several previous works. In this paper, we first determine the value of $b_2(n)$ for all $n$, which confirms a conjecture due to Buchanan et al. (JGT, 2026), and then show $b_3(n+1)=b_2(n)$ by which the value of $b_3(n)$ is determined for all $n$, that resolves a question posed by Leader and Tan (EJC, 2026).
Figures
Reference graph
Works this paper leans on
-
[2]
C. Buchanan, A. Clifton, E. Culver, J. Nie, J. O’Neill, P. Rombach and M. Yin, Odd covers of graphs,Journal of Graph Theory104 (2023), 420–439
work page 2023
-
[1]
L. Babai and P. Frankl, Linear Algebra Methods in Combinatorics: Part 1, Department of Computer Science, The University of Chicago, preliminary version, 1992
work page 1992
-
[3]
On odd covers of cliques and disjoint unions
C. Buchanan, A. Clifton, E. Culver, P. Frankl, J. Nie, K. Ozeki, P. Rombach and M. Yin, On odd covers of cliques and disjoint unions,Journal of Graph Theory, to appear; arXiv:2408.08598
-
[4]
C. Buchanan, C. Purcell and P. Rombach, Subgraph complementation and minimum rank, Electronic Journal of Combinatorics29 (2022), P1.38
work page 2022
-
[5]
Niel de Beaudrap, Decomposition of graphs as symmetric differences of copies ofK a,b, MathOverflow,https://mathoverflow.net/q/76043(version 2011-10-27)
work page 2011
-
[6]
R. L. Graham and H. O. Pollak, On the addressing problem for loop switching,Bell System Technical Journal50 (1971), 2495–2519
work page 1971
-
[7]
R. L. Graham and H. O. Pollak, On embedding graphs in squashed cubes, inGraph Theory and Applications, Lecture Notes in Mathematics, vol. 303, Springer, 1972, pp. 99–110
work page 1972
-
[8]
M. Kami´ nski, V. V. Lozin and M. Milaniˇ c, Recent developments on graphs of bounded clique-width,Discrete Applied Mathematics157 (2009), 2747–2761
work page 2009
Show all 11 references
-
[9]
Leader, L
I. Leader, L. Mili´ cevi´ c and T. S. Tan, Decomposing the completer-graph,Journal of Combinatorial Theory, Series A154 (2018), 21–31
2018
-
[10]
Leader and T
I. Leader and T. S. Tan, Odd covers of complete graphs and hypergraphs,European Journal of Combinatorics132 (2026), 104299
2026
-
[11]
Radhakrishnan, P
J. Radhakrishnan, P. Sen and S. Vishwanathan, Depth-3 arithmetic circuits forS 2 n(X) and extensions of the Graham–Pollack theorem, inFST TCS 2000: Foundations of Software Technology and Theoretical Computer Science, Lecture Notes in Computer Science, vol. 1974, Springer, 2000...
2000
Reviewed July 9, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.