Decomposing the complete r -graph
Document Type
Article
Publication Date
1-1-2018
Abstract
Let fr(n) be the minimum number of complete r-partite r-graphs needed to partition the edge set of the complete r-uniform hypergraph on n vertices. Graham and Pollak showed that f2(n)=n−1. An easy construction shows that fr(n)≤(1−o(1))(n⌊r/2⌋) and it has been unknown if this upper bound is asymptotically sharp. In this paper we show that fr(n)≤([formula presented]+o(1))(nr/2) for each even r≥4.
Keywords
Hypergraph, Decomposition, Graham–Pollak
Divisions
MathematicalSciences
Publication Title
Journal of Combinatorial Theory, Series A
Volume
154
Publisher
Elsevier
COinS