Improved bounds for the Graham-Pollak problem for hypergraphs (Q1691097)

Summary: 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) \leqslant (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.