Decomposing the complete r -graph
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 asymptoti...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Published: |
Elsevier
2018
|
| Subjects: |
| _version_ | 1825721703621197824 |
|---|---|
| author | Leader, Imre Milicevic, Luka Tan, Ta Sheng |
| author_facet | Leader, Imre Milicevic, Luka Tan, Ta Sheng |
| author_sort | Leader, Imre |
| collection | UM |
| description | 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. |
| first_indexed | 2024-03-06T05:54:24Z |
| format | Article |
| id | um.eprints-21539 |
| institution | Universiti Malaya |
| last_indexed | 2024-03-06T05:54:24Z |
| publishDate | 2018 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | um.eprints-215392019-06-26T03:22:22Z http://eprints.um.edu.my/21539/ Decomposing the complete r -graph Leader, Imre Milicevic, Luka Tan, Ta Sheng Q Science (General) QA Mathematics 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. Elsevier 2018 Article PeerReviewed Leader, Imre and Milicevic, Luka and Tan, Ta Sheng (2018) Decomposing the complete r -graph. Journal of Combinatorial Theory, Series A, 154. pp. 21-31. ISSN 0097-3165, DOI https://doi.org/10.1016/j.jcta.2017.08.008 <https://doi.org/10.1016/j.jcta.2017.08.008>. https://doi.org/10.1016/j.jcta.2017.08.008 doi:10.1016/j.jcta.2017.08.008 |
| spellingShingle | Q Science (General) QA Mathematics Leader, Imre Milicevic, Luka Tan, Ta Sheng Decomposing the complete r -graph |
| title | Decomposing the complete r -graph |
| title_full | Decomposing the complete r -graph |
| title_fullStr | Decomposing the complete r -graph |
| title_full_unstemmed | Decomposing the complete r -graph |
| title_short | Decomposing the complete r -graph |
| title_sort | decomposing the complete r graph |
| topic | Q Science (General) QA Mathematics |
| work_keys_str_mv | AT leaderimre decomposingthecompletergraph AT milicevicluka decomposingthecompletergraph AT tantasheng decomposingthecompletergraph |