New bounds on the Graham-Pollak theorem for hypergraphs
Discrete Mathematics
Summary
The authors study how to break down a complete hypergraph into simpler parts called complete r-partite r-uniform hypergraphs. They focus on the minimum number needed, denoted f_r(n), extending a classic result known for graphs. Previous work showed upper bounds for f_r(n) and introduced a limit value c_r related to the size of these partitions. The authors improve earlier results by lowering the smallest odd parameter r for which c_r is less than one from 113 to 85, and they provide better constant-factor bounds for these partitions.
Authors
Anand Babu
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) \leq (1+o(1)){n \choose \lfloor{\frac{r}{2}}\rfloor}$, which was subsequently improved to $f_r(n)\le \left[ \frac{r}{2} \left(\frac{14}{15}\right)^{r/4} +o(1) \right] \binom{n}{\lfloor r/2\rfloor}$. Let $c_r$ be $\displaystyle \lim_{n \to \infty}\frac{f_r(n)}{\binom{n}{\lfloor r/2 \rfloor}}$. It was known that $c_r<1$ for every even $r \geq 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)$.