Bounds for the Graham-Pollak Theorem for Hypergraphs

Abstract

Let $f_r(n)$ represent the minimum number of complete $r$-partite $r$-graphs 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$. An upper bound of $(1+o(1))\left(\genfrac{}{}{0ex}{}{n}{\lfloor \frac{r}{2}\rfloor }\right)$ was known. Recently this was improved to $\frac{14}{15}(1+o(1))\left(\genfrac{}{}{0ex}{}{n}{\lfloor \frac{r}{2}\rfloor }\right)$ for even $r\ge 4$. A bound of $[\frac{r}{2}(\frac{14}{15}{)}^{\frac{r}{4}}+o(1)](1+o(1))(\genfrac{}{}{0ex}{}{n}{\lfloor \frac{r}{2}\rfloor })$ was also proved recently. The smallest odd $r$ for which $c_r<1$ that was known was for $r=295$. In this note we improve this to $c_{113}<1$ and also give better upper bounds for $f_r(n)$, for small values of even $r$.

8 pages