New bounds on the Graham-Pollak theorem for hypergraphs

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)\le (1+o(1))\left(\genfrac{}{}{0ex}{}{n}{\lfloor \frac{r}{2}\rfloor }\right)$, which was subsequently improved to $f_r(n)\le \left[\frac{r}{2}{\left(\frac{14}{15}\right)}^{r/4}+o(1)\right]\left(\genfrac{}{}{0ex}{}{n}{\lfloor r/2\rfloor }\right)$. Let $c_r$ be $\underset{n\to \infty }{\lim }\frac{f_r(n)}{\left(\genfrac{}{}{0ex}{}{n}{\lfloor r/2\rfloor }\right)}$. It was known that $c_r<1$ for every even $r\ge 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)$.

10 pages