Improved Bounds for the Graham-Pollak Problem for Hypergraphs

Abstract

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)\le (1+o(1))\left(\genfrac{}{}{0ex}{}{n}{\lfloor r/2\rfloor }\right)$, and we write $c_r$ for the least number such that $f_r(n)\le c_r(1+o(1))\left(\genfrac{}{}{0ex}{}{n}{\lfloor r/2\rfloor }\right)$. It was known that $c_r<1$ for each even $r\ge 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\to 0$, answering another open problem.