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 Sep 6, 2024
Page view(s)
1
checked on Sep 7, 2024
Google ScholarTM
Check
Altmetric
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.