Packing Loose Hamilton Cycles

Asaf Ferber, Kyle Luh, Daniel Montealegre, Oanh Nguyen

Research output: Contribution to journalArticle

Abstract

A subset C of edges in a k-uniform hypergraph H is a loose Hamilton cycle if C covers all the vertices of H and there exists a cyclic ordering of these vertices such that the edges in C are segments of that order and such that every two consecutive edges share exactly one vertex. The binomial random k-uniform hypergraph H k n,p has vertex set [n] and an edge set E obtained by adding each k-tuple e ∈ ([n] k) to E with probability p, independently at random. Here we consider the problem of finding edge-disjoint loose Hamilton cycles covering all but o(|E|) edges, referred to as the packing problem. While it is known that the threshold probability of the appearance of a loose Hamilton cycle in H k n,p is {equation presented} the best known bounds for the packing problem are around p = polylog(n)/n. Here we make substantial progress and prove the following asymptotically (up to a polylog(n) factor) best possible result: for {equation presented}, a random k-uniform hypergraph H k n,p with high probability contains {equation presented} edge-disjoint loose Hamilton cycles. Our proof utilizes and modifies the idea of 'online sprinkling' recently introduced by Vu and the first author.

Original languageEnglish (US)
Pages (from-to)839-849
Number of pages11
JournalCombinatorics Probability and Computing
Volume26
Issue number6
DOIs
StatePublished - Nov 1 2017

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Statistics and Probability
  • Computational Theory and Mathematics
  • Applied Mathematics

Keywords

  • 2010 Mathematics subject classification:Primary 05C80 Secondary 05C65

Fingerprint Dive into the research topics of 'Packing Loose Hamilton Cycles'. Together they form a unique fingerprint.

  • Cite this

    Ferber, A., Luh, K., Montealegre, D., & Nguyen, O. (2017). Packing Loose Hamilton Cycles. Combinatorics Probability and Computing, 26(6), 839-849. https://doi.org/10.1017/S0963548317000402