New bounds on the Graham-Pollak theorem for hypergraphs
Abstract
For a fixed r, let fr(n) denote the minimum number of complete r-partite r-uniform hypergraphs whose edge sets partition the complete r-uniform hypergraph on n vertices. The Graham-Pollak theorem asserts that f2(n)=n−1. Let cr be the smallest constant such that fr(n)≤ cr(1+o(1))binomn⌊ r/2⌋. We give two constructions that improve upper bounds for fr(n). The first partitions E(K4)× E(K17) into $44$ products of edge sets of complete bipartite graphs and yields c4≤11/12, improving the previous bound of c4≤14/15. The second gives an asymptotically improved exact cover for odd r. Combining these constructions, we prove that cr<1 for every odd integer r≥65, which improves upon the previous computer-assisted result of $113$. We further obtain the improved asymptotic bound cr≤ r/15(11/12)r/4+o(1) for general r. These results narrow the gap towards resolving the major open problem of determining whether c5<1.
Related
- A note on the Kővári--Sós--Turán theorem for stable hypergraphs
- A Fan-Type Theorem for Hamiltonian Berge Cycles in 3-Uniform Hypergraphs
- The upper bounds on occupancy fraction and variance fraction for linear regular uniform hypergraphs
- Quadratic bounds for intersecting hypergraphs: An affirmative answer to a question of Duke and Erdős
- Polynomial-in-r bounds for forbidden traces of uniform hypergraphs
BibTeX
@misc{babu2026bounds,
title = {{New bounds on the Graham-Pollak theorem for hypergraphs}},
author = {Anand Babu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2607.15658},
eprint = {2607.15658},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.15658},
}
RIS
TY - UNPB
TI - New bounds on the Graham-Pollak theorem for hypergraphs
AU - Anand Babu
PY - 2026
DA - 2026/09/14
PB - arXiv
DO - 10.48550/arxiv.2607.15658
UR - https://arxiv.org/abs/2607.15658
AB - For a fixed r, let f_r(n) denote the minimum number of complete r-partite r-uniform hypergraphs whose edge sets partition the complete r-uniform hypergraph on n vertices. The Graham-Pollak theorem asserts that f_2(n)=n−1. Let c_r be the smallest constant such that f_r(n)≤ c_r(1+o(1))binomn⌊ r/2⌋. We give two constructions that improve upper bounds for f_r(n). The first partitions E(K_4)× E(K_17) into $44$ products of edge sets of complete bipartite graphs and yields c_4≤11/12, improving the previous bound of c_4≤14/15. The second gives an asymptotically improved exact cover for odd r. Combining these constructions, we prove that c_r<1 for every odd integer r≥65, which improves upon the previous computer-assisted result of $113$. We further obtain the improved asymptotic bound c_r≤ r/15(11/12)^r/4+o(1) for general r. These results narrow the gap towards resolving the major open problem of determining whether c_5<1.
ER -