Decompositions of complete uniform hypergraphs into Hamilton Berge cycles

Daniela Kühn*, Deryk Osthus

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

13 Citations (Scopus)

Abstract

In 1973 Bermond, Germa, Heydemann and Sotteau conjectured that if n divides (nk), 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 v1,e1,v2,...,vn,en of distinct vertices vi and distinct edges e i so that each e i contains vi and vi+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.

Original languageEnglish
Pages (from-to)128-135
Number of pages8
JournalJournal of Combinatorial Theory, Series A
Volume126
Issue number1
DOIs
Publication statusPublished - 1 Jan 2014

Keywords

  • Berge cycles
  • Hamilton cycles
  • Hamilton decompositions
  • Hypergraphs

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Theoretical Computer Science
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Decompositions of complete uniform hypergraphs into Hamilton Berge cycles'. Together they form a unique fingerprint.

Cite this