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) \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)$.
이 뉴스, 어떠셨어요?
탭 한 번으로 반응 · 로그인 불필요