Authors: | Leader, Imre Milićević, Luka Tan, Ta Sheng |
Title: | Decomposing the complete r-graph | Journal: | Journal of Combinatorial Theory. Series A | Volume: | 154 | First page: | 21 | Last page: | 31 | Issue Date: | 1-Feb-2018 | Rank: | M21 | ISSN: | 0097-3165 | DOI: | 10.1016/j.jcta.2017.08.008 | 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: | Decomposition | Graham–Pollak | Hypergraph | Publisher: | Elsevier | Project: | Ministry of Higher Education of Malaysia, FRGS grant FP048-2014B |
Show full item record
SCOPUSTM
Citations
7
checked on Nov 7, 2024
Page view(s)
18
checked on Nov 8, 2024
Google ScholarTM
Check
Altmetric
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.