New bounds on the Graham-Pollak theorem for hypergraphs

Anand Babu

REVIEW 1 major objections 3 minor 20 references

New bounds on the Graham-Pollak theorem for hypergraphs

T0 review · 1 major / 3 minor · reviewed 2026-08-01 · deepseek-v4-flash

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

Pith's one-line read For every odd r ≥ 85, the complete r-uniform hypergraph on n vertices can be edge-partitioned into at most c_r (1+o(1)) binomial(n, floor(r/2)) complete r-partite r-graphs with c_r < 1, improving the previous threshold of 113.

desk verdict Genuine incremental progress (113 to 85) with a clean explicit construction for r=85, but Theorem 1 leans on an unstated Leader–Tan decomposition and Corollary 2 has an algebraic inversion; fixable and worth refereeing. read the letter →

arxiv 2607.15658 v1 pith:VVLVZSYH submitted 2026-07-17 math.CO cs.DM

Anand Babu This is my paper · ORCID

classification math.COcs.DM MSC 05C6505C70

keywords Graham-Pollaktheoremhypergraphsedgepartitioncompleter-partiteexactcoverupperboundsbicliqueasymptoticconstants

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper improves the known upper bounds in the Graham–Pollak problem for hypergraphs: the minimum number of complete r-partite r-uniform hypergraphs needed to partition the edge set of the complete r-uniform hypergraph on n vertices. For odd r, the previous best result guaranteed the normalized constant c_r is below 1 only for r ≥ 113; this paper lowers that threshold to r ≥ 85. The improvement comes from treating the remaining edge classes collectively instead of individually, grouping the troublesome 'three-in-one-class' edge families according to a partition of the index set and covering each group with a single exact cover. The same construction also sharpens the asymptotic leading constant in the upper bound for f_r(n), replacing the previous r/2 (14/15)^{r/4} by a smaller constant times r (14/15)^{r/4}.

What carries the argument

The key mechanism is the exact-cover lemma (Lemma 5) that, given a partition P_1∪...∪P_ℓ of [d], produces a block decomposition of the union of the '3-in-one-class, 2-in-the-rest' edge families and the '1-in-U, 2-in-each-V_i' family, using at most Σ_j n^{s_j} g(n)^{(d-s_j)/2} blocks (with an extra factor n when d−s_j is odd), where g(n) ≤ (14/15+o(1)) n^2 is the known upper bound for partitioning E(K_n)×E(K_n). The construction picks one anchor vertex from each class in a group and forms blocks whose parts are the preceding vertices, the anchor, and a final part made of all following vertices; taking products of these covers over all groups handles the full family. This collective treatment

What would settle it

Test the imported decomposition on a small case: for r=5 (d=2) and k=3 vertex classes, brute-force the minimum number of blocks needed to cover all edges with odd intersection in at least three classes; if this number grows faster than a constant times n^{d−1}, Theorem 1 fails. Alternatively, run Lemma 5's construction for s=1 or 2 with small n and check whether the actual block count exceeds the claimed n^s g(n)^{(d−s)/2}.

Watch

Extended reading notes

Core claim

The paper establishes Theorem 1: for each odd r = 2d+1 and every fixed k, f_r(kn) is at most (1+o(1)) choose(kn,d) times the minimum, over all partitions P_1∪...∪P_ℓ of [d], of Σ_j (14/15)^{⌊(d-|P_j|)/2⌋} plus a term ε_k that tends to 0 as k grows. The proof uses an exact-cover construction (Lemmas 1–5) that covers, for each group P_j, the family of edges that take three vertices from one class in P_j and two from every other of the d classes, using products of simple blocks of the form {predecessors of x_i}, {x_i}, ..., {followers of x_i}, combined with the known decomposition of E(K_n)×E(K_n) into at most (14/15+o(1))n^2 blocks. For d=42 the partition with group sizes 20 and 22 gives (14/1

Load-bearing premise

The proof rests on a cited but unproved decomposition result from an earlier paper, which asserts that the edge classes with odd intersection in at least three vertex classes (and similarly those with odd intersection in exactly one of at most d−1 classes) can be partitioned into O(n^{d−1}) blocks; if that imported lemma is false or misapplied, the main upper bound collapses.

Editorial extensions

If this is right

For every odd r ≥ 85, the trivial upper bound (1+o(1)) choose(n, floor(r/2)) is provably not optimal: c_r < 1.
The leading constant in the upper bound for f_r(n) is reduced by a constant factor; for large r the new coefficient is (15/14)^{3/4} e ln(15/14)/4 ≈ 0.048 times r (14/15)^{r/4}, versus the previous (1/2) r (14/15)^{r/4}.
Since c_r ≤ c_{r+1}, the odd-r improvements also give strictly smaller constants for even r at least 84.
The construction is explicit, so it yields an actual block partition of the edge set, not merely an existence statement.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A search over all partitions of [d] for d < 42 could likely lower the threshold below 85; the paper shows 85 works but does not claim it is optimal.
The same grouping strategy may apply to related decomposition problems — odd covers, multicoverings, or list-covering variants — where exceptional edge classes are currently handled one by one.
The optimisation in Corollary 2 assumes all group sizes are equal; allowing unequal sizes (as in the r=85 case) could yield a still smaller asymptotic constant, which the paper does not explore.
The proof is asymptotic: the ε_k term means the bound only beats the trivial constant for n sufficiently large relative to k, so the result does not give explicit finite-n bounds.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

Short version: this note is a real, incremental improvement on a niche problem. It lowers the smallest odd r for which c_r<1 from 113 to 85 and claims a constant-factor improvement in the known upper bound. The core construction for r=85 (partition sizes 20 and 22) is explicit, the arithmetic checks out, and Lemmas 1–5 are clean and correct. That part is worth taking seriously.

The main new idea is to group the leftover edge classes according to the position of the 3-part and cover each group in one pass, rather than treating them individually. That is a natural extension of the Leader–Tan framework, and it produces the quoted threshold.

Where the paper gets soft:

First, Theorem 1's proof is built on an imported decomposition from the proof of Theorem 1 of [13]. The assertion is stated in one sentence, no lemma, no hypotheses checked, and the constants C and C' are said to depend on d and k without further control. In the final absorption, epsilon_k is roughly d!C'/k, so for epsilon_k->0 you need C'=o(k). That is not established. This is not a stylistic complaint: it is the point where the new lemmas connect to the old theorem. If the cited decomposition does not behave that way, the upper bound collapses. The fix is to pull the exact statement out of [13] and verify the constant dependence.

Second, Corollary 1's "similarly for r>=85" is wrong at r=85: the balanced partition with |P1|=|P2|=21 gives 2(14/15)^10, about 1.002, not less than 1. The separate 20+22 construction handles r=85, so the sentence should say r>=87.

Third, Corollary 2's algebra is muddled. The critical value of l should be d ln(15/14)/2, not d/(2 ln(15/14)), and the exponent after substitution does not match the l they state. As written, the derivation is internally inconsistent. The final formula does coincide with the correct minimizer up to o(1), so I suspect typos, but they need to be fixed before a reader can trust the constant-factor claim.

On the citation pattern: the reliance on [12,13] is explicit, and the self-citation [3] is just the previous threshold. No circularity.

Bottom line: this is a solid, incremental paper that deserves serious refereeing, but the referee should send it back for a rewrite of Theorem 1's imported lemma and Corollaries 1–2. If the author fixes those, the result is likely correct. Good for a reading group that wants a case study in checking constants.

Referee Report

1 major / 3 minor

Summary. The paper studies f_r(n), the minimum number of complete r-partite r-uniform hypergraphs needed to partition the edge set of the complete r-uniform hypergraph K_n^r. For fixed r, the asymptotic leading constant c_r = lim_n f_r(n)/binom(n, floor(r/2)) is known to satisfy c_r < 1 for all even r >= 4 and for all odd r >= 113. The paper claims two improvements: (1) c_r < 1 for every odd r >= 85, via an explicit exact-cover construction that partitions the d = (r-1)/2 vertex classes into two blocks of sizes 20 and 22 when r=85; and (2) an asymptotic upper bound for c_r with a constant factor roughly e ln(15/14)/4 * r * (14/15)^{r/4}, improving the earlier r/2 (14/15)^{r/4}. The proof is built on several elementary lemmas (Lemmas 1--5) that explicitly construct exact covers for the 'clean' edge classes, together with an imported decomposition from Leader and Tan [13] for all remaining edge classes.

Significance. If the claims hold, this is a genuine, if incremental, advance: lowering the odd-r threshold from 113 to 85 is a concrete improvement, and the asymptotic constant for large odd r is significantly smaller than the previous r/2 (14/15)^{r/4}. The paper's own Lemmas 1--5 are explicit and checkable, and the idea of grouping the remaining edge classes according to a partition of [d] is a neat contribution. However, the main theorem depends on a nontrivial decomposition imported from the proof of a theorem in [13], and the proof as written does not control the constants in that decomposition sufficiently to justify the stated epsilon_k -> 0. The derivation of the asymptotic constant in Corollary 2 also contains algebraic slips. The central construction is plausible, but the manuscript needs substantial repair before the claims can be accepted.

major comments (1)

[Section 2, Corollary 2 proof] The optimization argument contains a serious algebraic error. From F'(ell) = a^p (1 - d/(2ell) ln(15/14)), setting F'(ell)=0 gives ell = (d ln(15/14))/2, not ell = d/(2 ln(15/14)). The displayed substitution uses the reciprocal value, and the subsequent simplification using (14/15)^{-1/ln(15/14)} = e is inconsistent with the substituted value. Thus the derivation as written does not establish the claimed constant. In addition, the proof replaces floor((d-s_j)/2) by (d-s_j-1)/2 without treating parity; when d-s_j is even this underestimates the corresponding summand by a factor (14/15)^{1/2}, which is not o(1) and can affect the claimed leading constant. The final formula may be salvageable, but the proof must be redone carefully.

minor comments (3)

[Corollary 1, last sentence] The statement 'Similarly for r >= 85, considering the partition P = P1 ∪ P2 with |P1| = floor(d/2) and |P2| = ceil(d/2), we have c_r < 1' is false for r = 85: with d = 42 the floor/ceil partition gives 21 and 21, yielding 2*(14/15)^10 ≈ 1.002 > 1. The correct statement is 'for r >= 87' (as the special 20/22 partition already handles r = 85).
[Lemma 5 proof] The wording 'Applying Lemma 2 with P = P_i, for each 1 <= i != j <= ell' is confusing: j first appears as the index in 'Apply Lemma 4 with P = P_j', but the intent is to fix one j and cover the other F_i using Lemma 2. Please rewrite this sentence for clarity.
[Theorem 1 / corollaries] Theorem 1 gives a bound for f_r(kn) when n is the size of each vertex class. To pass to arbitrary N, one should explicitly say that f_r(N) <= f_r(k ceil(N/k)) and then use monotonicity; this is standard but should be stated. Also, there are small typographical issues in the abstract (e.g., 'It was known that f_r(n) <= (1+o(1)){n choose floor(r/2)}' missing the binomial notation).

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: Theorem 1 is an explicit block construction whose inputs are external prior bounds, not the target result.

full rationale

I find no circular step. Theorem 1's bound is obtained by an explicit exact-cover construction (Lemmas 1–5) whose counting uses only n^s, g(n), and binomial(k,d); the numerical claim c_r < 1 for r = 85 follows directly from (14/15)^11 + (14/15)^10 ≈ 0.9698 < 1, with epsilon_k chosen to make the sum below 1. The only imported ingredients are (i) the black-box bound g(n) ≤ (14/15+o(1))n^2 from Leader–Milićević–Tan [12] and (ii) a decomposition of the 'bad' edge classes 'from the proof of Theorem 1 of Leader and Tan [13]'. Neither is authored by the present paper's author in a way that assumes the target result, and neither is fitted to the claimed c_r value, so these are independent external supports rather than circular inputs. The only self-citation is [3], used as the previous threshold being improved, not as a load-bearing proof step. The paper's Corollary 2 is a straightforward unconstrained minimization of a displayed function and does not rename a fitted quantity as a prediction. I note the manuscript's reliance on the unstated constants C, C' from [13] is a correctness risk: the proof needs C' = o(k) for epsilon_k -> 0, and the text only says the constants depend on d and k. However, an unproved external citation is a gap in verification, not circularity, because there is no indication that [13] assumes the conclusion claimed here or that the present construction reduces to its own input by definition.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The paper introduces no new entities or fitted constants. It relies on two published external bounds ([12] and [13]) and standard combinatorial covering arguments. The partition sizes (20,22 for r=85; floor/ceil for larger r) are explicit construction choices, not hidden fitted parameters.

assumptions (3)

domain assumption g(n) ≤ (14/15 + o(1)) n^2, where g(n) is the minimum number of products of complete bipartite graphs needed to partition E(K_n) × E(K_n)
Imported from Leader-Milićević-Tan [12]; used in Theorem 1 to replace each g(n) in Lemmas 2, 4, 5 with (14/15+o(1)) n^2.
domain assumption The set of r-edges with odd intersection in at least three vertex classes can be decomposed into C n^{d-1} complete r-partite r-graphs, and the set with odd intersection in exactly one of at most d-1 vertex classes into C' k^{d-1} n^d blocks
Quoted as following from the proof of Theorem 1 of Leader-Tan [13]; this is the key imported lemma that lets the proof ignore all edge classes except the two 'leading term' profiles.
standard math Standard properties of exact covers and products of complete multipartite hypergraphs: the product of exact covers of two families of partial edges is an exact cover of the product family, and restricting/blowing up vertex classes preserves the block structure
Used implicitly throughout Lemmas 1-5 and Theorem 1; no special proof is required for readers of this literature.

how reviews work

0 comments

Cite this review

Pith. "Pith review of New bounds on the Graham-Pollak theorem for hypergraphs." pith.science (2026). https://pith.science/paper/VVLVZSYH

@misc{pith2026260715658,
  author       = {Pith},
  title        = {Pith review of: New bounds on the Graham-Pollak theorem for hypergraphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VVLVZSYH}},
  note         = {Machine review of arXiv:2607.15658}
}

abstract

For a fixed $r$, let $f_r(n)$ denote the minimum number of complete $r$-partite $r$-uniform hypergraphs required to partition the edge set of the complete $r$-uniform hypergraph on $n$ vertices. The Graham-Pollak theorem states that $f_2(n)=n-1$. It was known that $f_r(n) \leq (1+o(1)){n \choose \lfloor{\frac{r}{2}}\rfloor}$, which was subsequently improved to $f_r(n)\le \left[ \frac{r}{2} \left(\frac{14}{15}\right)^{r/4} +o(1) \right] \binom{n}{\lfloor r/2\rfloor}$. Let $c_r$ be $\displaystyle \lim_{n \to \infty}\frac{f_r(n)}{\binom{n}{\lfloor r/2 \rfloor}}$. It was known that $c_r<1$ for every even $r \geq 4$, while for odd $r$ the smallest known value satisfying $c_r<1$ was $113$. In this note we lower this to $85$ and also provide a constant-factor improvement in the known bounds for $f_r(n)$.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

20 extracted references · 2 linked inside Pith

[13]

Leader and T

I. Leader and T. S. Tan. Improved bounds for the Graham-Pollak problem for hypergraphs.The Electronic Journal of Combinatorics, 25(1):1–4, 2018

2018
[3]

BoundsfortheGraham-Pollaktheoremfor hypergraphs.Discrete Mathematics, 342(11):3177–3181, 2019

A.BabuandS.Vishwanathan. BoundsfortheGraham-Pollaktheoremfor hypergraphs.Discrete Mathematics, 342(11):3177–3181, 2019

2019
[1]

N. Alon. Decomposition of the completer-graph into completer-partite r-graphs.Graphs and Combinatorics, 2(1):95–100, 1986

1986
[2]

Babai and P

L. Babai and P. Frankl.Linear algebra methods in combinatorics: with applica- tions to geometry and computer science. University of Chicago, 1992

1992
[4]

Multicoveringhypergraphs.DiscreteMath- ematics, 344(6):112386, 2021

A.BabuandS.Vishwanathan. Multicoveringhypergraphs.DiscreteMath- ematics, 344(6):112386, 2021

2021
[5]

Babu and S

A. Babu and S. Vishwanathan. Improved bounds for covering hyper- graphs.arXiv preprint arXiv:2208.12589, 2022

arXiv 2022
[6]

Buchanan, A

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.arXiv preprint arXiv:2408.08598, 2024

arXiv 2024
[7]

Buchanan, A

C. Buchanan, A. Clifton, E. Culver, J. Nie, J. O’Neill, P. Rombach, and M. Yin. Odd covers of graphs.Journal of Graph Theory, 104(2):420–439, 2023

2023

Show all 20 references

[8]

S. M. Cioabă, A. Kündgen, and J. Verstraëte. On decompositions of com- plete hypergraphs.Journal of Combinatorial Theory, Series A, 116(7):1232– 1234, 2009

2009
[9]

S. M. Cioabă and M. Tait. Variations on a theme of Graham and Pollak. Discrete Mathematics, 313(5):665–676, 2013

2013
[10]

R. L. Graham and H. O. Pollak. On the addressing problem for loop switching.Bell System Technical Journal, 50(8):2495–2519, 1971

1971
[11]

Onembeddinggraphsinsquashedcubes

R.L.GrahamandH.O.Pollak. Onembeddinggraphsinsquashedcubes. InGraph Theory and Applications, pages 99–110. Springer, 1972

1972
[12]

Leader, L

I. Leader, L. Milićević, and T. S. Tan. Decomposing the completer-graph. Journal of Combinatorial Theory, Series A, 154(Supplement C):21–31, 2018

2018
[14]

Odd covers of complete graphs and hypergraphs.European Journal of Combinatorics, 132:104299, 2026

Imre Leader and Ta Sheng Tan. Odd covers of complete graphs and hypergraphs.European Journal of Combinatorics, 132:104299, 2026

2026
[15]

G. W. Peck. A new proof of a theorem of Graham and Pollak.Discrete Mathematics, 49(3):327–328, 1984. 9

1984
[16]

Radhakrishnan, P

J. Radhakrishnan, P. Sen, and S. Vishwanathan. Depth-3 arithmetic cir- cuits forS 2 n(x)and extensions of the Graham-Pollak theorem. InFounda- tionsofSoftwareTechnologyandTheoreticalComputerScience,pages176–187. Springer, 2000

2000
[17]

Orderedbicliquepartitionsandcommunication complexity problems.Discrete Applied Mathematics, 184:248–252, 2015

Y.ShigetaandK.Amano. Orderedbicliquepartitionsandcommunication complexity problems.Discrete Applied Mathematics, 184:248–252, 2015

2015
[18]

Tverberg

H. Tverberg. On the decomposition ofKn into complete bipartite graphs. Journal of Graph Theory, 6(4):493–494, 1982

1982
[19]

Vishwanathan

S. Vishwanathan. A polynomial space proof of the Graham–Pollak theo- rem.Journal of Combinatorial Theory, Series A, 115(4):674–676, 2008

2008
[20]

Vishwanathan

S. Vishwanathan. A counting proof of the Graham–Pollak theorem.Dis- crete Mathematics, 313(6):765–766, 2013. 10

2013

Pith tools

Reviewed August 1, 2026 · model on record in the stance chip above.

[1] [13]

Leader and T

I. Leader and T. S. Tan. Improved bounds for the Graham-Pollak problem for hypergraphs.The Electronic Journal of Combinatorics, 25(1):1–4, 2018

2018

[2] [3]

BoundsfortheGraham-Pollaktheoremfor hypergraphs.Discrete Mathematics, 342(11):3177–3181, 2019

A.BabuandS.Vishwanathan. BoundsfortheGraham-Pollaktheoremfor hypergraphs.Discrete Mathematics, 342(11):3177–3181, 2019

2019

[3] [1]

N. Alon. Decomposition of the completer-graph into completer-partite r-graphs.Graphs and Combinatorics, 2(1):95–100, 1986

1986

[4] [2]

Babai and P

L. Babai and P. Frankl.Linear algebra methods in combinatorics: with applica- tions to geometry and computer science. University of Chicago, 1992

1992

[5] [4]

Multicoveringhypergraphs.DiscreteMath- ematics, 344(6):112386, 2021

A.BabuandS.Vishwanathan. Multicoveringhypergraphs.DiscreteMath- ematics, 344(6):112386, 2021

2021

[6] [5]

Babu and S

A. Babu and S. Vishwanathan. Improved bounds for covering hyper- graphs.arXiv preprint arXiv:2208.12589, 2022

arXiv 2022

[7] [6]

Buchanan, A

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.arXiv preprint arXiv:2408.08598, 2024

arXiv 2024

[8] [7]

Buchanan, A

C. Buchanan, A. Clifton, E. Culver, J. Nie, J. O’Neill, P. Rombach, and M. Yin. Odd covers of graphs.Journal of Graph Theory, 104(2):420–439, 2023

2023