2026/07/17 by Anand Babu
#math.CO #cs.DM
For a fixed r, let fr(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 f2(n)=n-1. It was known that fr(n) ≤ (1+o(1))n \choose \lfloor(r)/(2)\rfloor, which was subsequently improved to fr(n)≤ [ (r)/(2) ((14)/(15))r/4 +o(1) ] \binomn\lfloor r/2\rfloor. Let cr be limn → ∞\fracfr(n)\binomn\lfloor r/2 \rfloor. It was known that cr<1 for every even r ≥ 4, while for odd r the smallest known value satisfying cr<1 was 113. In this note we lower this to 85 and also provide a constant-factor improvement in the known bounds for fr(n).