2017/08/06 by Leader, Imre, Tan, Ta Sheng · 1 citation
#05C70 #05D05 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1708.01898
For a fixed r, let fr(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 f2(n)=n-1. An easy construction shows that fr(n) ≤ (1+o(1))\binomn\lfloor r/2 \rfloor, and we write cr for the least number such that fr(n) ≤ cr (1+o(1))\binomn\lfloor r/2 \rfloor. It was known that cr < 1 for each even r ≥ 4, but this was not known for any odd value of r. In this short note, we prove that c295<1. Our method also shows that cr → 0, answering another open problem.