Decompositions of complete uniform hypergraphs into Hamilton Berge cycles

作者：Kuehn Daniela; Osthus Deryk

来源：Journal of Combinatorial Theory - Series A, 2014, 126: 128-135.

DOI：10.1016/j.jcta.2014.04.010

• Hypergraphs
• Hamilton cycles
• Hamilton decompositions
• Berge cycles

In 1973 Bermond, Germa, Heydemann and Sotteau conjectured that if n divides ((n)(k)) , then the complete k-uniform hypergraph on n vertices has a decomposition into Hamilton Berge cycles. Here a Berge cycle consists of an alternating sequence v(1), e(1) v(2,)..., v(n), e(n) of distinct vertices v(i) and distinct edges e(i) so that each e(i) contains v(i) and v(i+1). So the divisibility condition is clearly necessary. In this note, we prove that the conjecture holds whenever k >= 4 and n >= 30. Our argument is based on the Kruskal-Katona theorem. The case when k = 3 was already solved by Verrall, building on results of Bermond.

• 出版日期2014-8