Hostname: page-component-745bb68f8f-s22k5 Total loading time: 0 Render date: 2025-02-06T18:58:30.378Z Has data issue: false hasContentIssue false
  • English
  • Français

Packing Loose Hamilton Cycles

Published online by Cambridge University Press:  01 August 2017

ASAF FERBER ,
KYLE LUH ,
DANIEL MONTEALEGRE  and
OANH NGUYEN
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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 Hkn,p has vertex set [n] and an edge set E obtained by adding each k-tuple e ∈ ($\binom{[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 Hkn,p is

$p=\Theta\biggl(\frac{\log n}{n^{k-1}}\biggr),$
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 p ≥ logCn/nk−1, a random k-uniform hypergraph Hkn,p with high probability contains
$N:=(1-o(1))\frac{\binom{n}{k}p}{n/(k-1)}$
 edge-disjoint loose Hamilton cycles.

Our proof utilizes and modifies the idea of ‘online sprinkling’ recently introduced by Vu and the first author.

Keywords

Primary 05C80Secondary 05C65
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 26 , Issue 6 , November 2017 , pp. 839 - 849
Copyright
Copyright © Cambridge University Press 2017 

References

[1] Dudek, A. and Frieze, A. (2011) Loose Hamilton cycles in random uniform hypergraphs. Electron. J. Combin. 18 P48.Google Scholar
[2] Dudek, A., Frieze, A., Loh, P.-S. and Speiss, S. (2012) Optimal divisibility conditions for loose Hamilton cycles in random hypergraphs. Electron. J. Combin. 19 P44.Google Scholar
[3] Ferber, A. (2015) Closing gaps in problems related to Hamilton cycles in random graphs and hypergraphs. Electron. J. Combin. 22 P1.61.Google Scholar
[4] Ferber, A., Kronenberg, G. and Long, E. (2015) Packing, Counting and Covering Hamilton cycles in random directed graphs. Electron. Notes Discrete Math. 49 813–819.Google Scholar
[5] Ferber, A. and Vu, V. (2016) Packing perfect matchings in random hypergraphs. arXiv preprint arXiv:1606.09492.Google Scholar
[6] Frieze, A. (2010) Loose Hamilton cycles in random 3-uniform hypergraphs. Electron. J. Combin. 17 N28.Google Scholar
[7] Frieze, A. and Krivelevich, M. (2005) On packing Hamilton cycles in ϵ-regular graphs. J. Combin. Theory Ser. B 94 159–172.CrossRefGoogle Scholar
[8] Frieze, A. and Krivelevich, M. (2012) Packing Hamilton cycles in random and pseudo-random hypergraphs. Random Struct. Alg. 41 1–22.Google Scholar
[9] Knox, F., Kühn, D. and Osthus, D. (2015) Edge-disjoint Hamilton cycles in random graphs. Random Struct. Alg. 46 397–445.CrossRefGoogle Scholar
[10] Krivelevich, M. and Samotij, W. (2012) Optimal packings of Hamilton cycles in sparse random graphs. SIAM J. Discrete Math. 26 964–982.CrossRefGoogle Scholar
[11] McDiarmid, C. (1998) Concentration. In Probabilistic Methods for Algorithmic Discrete Mathematics, Springer, pp. 195–248.Google Scholar