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.