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 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)\le c_r(1+o(1))\left(\genfrac{}{}{0ex}{}{n}{\lfloor r/2\rfloor }\right)$. We give two constructions that improve upper bounds for $f_r(n)$. The first partitions $E(K_4)\times E(K_{17})$ into $44$ products of edge sets of complete bipartite graphs and yields $c_4\le 11/12$, improving the previous bound of $c_4\le 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\ge 65$, which improves upon the previous computer-assisted result of $113$. We further obtain the improved asymptotic bound $c_r\le \frac{r}{15}{\left(\frac{11}{12}\right)}^{r/4}+o(1)$ for general $r$. These results narrow the gap towards resolving the major open problem of determining whether $c_5<1$.

arXiv comment15 pages