Bounds for the Graham–Pollak theorem for hypergraphs

Abstract Let f r ( n ) represent the minimum number of complete r -partite r -graphs 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 . An upper bound of ( 1 + o ( 1 ) ) n ⌊ r 2 ⌋ was known. Recently this was improved to 14 15 ( 1 + o ( 1 ) ) n ⌊ r 2 ⌋ for even r ≥ 4 . A bound of [ r 2 ( 14 15 ) r 4 + o ( 1 ) ] ( 1 + o ( 1 ) ) n ⌊ r 2 ⌋ was also proved recently. Let c r be the limit of f r ( n ) n ⌊ r 2 ⌋ as n → ∞ . The smallest odd r for which c r 1 that was known was for r = 295 . In this note we improve this to c 113 1 and also give better upper bounds for f r ( n ) , for small values of even r .