For a fixed $r$, let $f_r(n)$ denote the minimum number of complete $r$-partite $r$-graphs needed to partition the complete $r$-graph on $n$ vertices. The Graham-Pollak theorem asserts that $f_2(n)=n-1$. An easy construction shows that $f_r(n) \leq (1+o(1))\binom{n}{\lfloor r/2 \rfloor}$, and we write $c_r$ for the least number such that $f_r(n) \leq c_r (1+o(1))\binom{n}{\lfloor r/2 \rfloor}$.It was known that $c_r < 1$ for each even $r \geq 4$, but this was not known for any odd value of $r$. In this short note, we prove that $c_{295}<1$. Our method also shows that $c_r \rightarrow 0$, answering another open problem.
@article{10_37236_7206,
author = {Imre Leader and Ta Sheng Tan},
title = {Improved bounds for the {Graham-Pollak} problem for hypergraphs},
journal = {The electronic journal of combinatorics},
year = {2018},
volume = {25},
number = {1},
doi = {10.37236/7206},
zbl = {1386.05157},
url = {http://geodesic.mathdoc.fr/articles/10.37236/7206/}
}
TY - JOUR
AU - Imre Leader
AU - Ta Sheng Tan
TI - Improved bounds for the Graham-Pollak problem for hypergraphs
JO - The electronic journal of combinatorics
PY - 2018
VL - 25
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/7206/
DO - 10.37236/7206
ID - 10_37236_7206
ER -
%0 Journal Article
%A Imre Leader
%A Ta Sheng Tan
%T Improved bounds for the Graham-Pollak problem for hypergraphs
%J The electronic journal of combinatorics
%D 2018
%V 25
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/7206/
%R 10.37236/7206
%F 10_37236_7206
Imre Leader; Ta Sheng Tan. Improved bounds for the Graham-Pollak problem for hypergraphs. The electronic journal of combinatorics, Tome 25 (2018) no. 1. doi: 10.37236/7206
