Optimal divisibility conditions for loose Hamilton cycles in random hypergraphs (Q1953356)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Optimal divisibility conditions for loose Hamilton cycles in random hypergraphs |
scientific article |
Statements
Optimal divisibility conditions for loose Hamilton cycles in random hypergraphs (English)
0 references
7 June 2013
0 references
Summary: In the random \(k\)-uniform hypergraph \(H^{(k)}_{n,p}\) of order \(n\), each possible \(k\)-tuple appears independently with probability \(p\). A loose Hamilton cycle is a cycle of order \(n\) in which every pair of consecutive edges intersects in a single vertex. It was shown by \textit{A. Frieze} [Electron. J. Comb. 17, No. 1, Research Paper N28, 4 p. (2010; Zbl 1189.05117)] that if \(p\geq c(\log n)/n^2\) for some absolute constant \(c>0\), then a.a.s. \(H^{(3)}_{n,p}\) contains a loose Hamilton cycle, provided that \(n\) is divisible by 4. Subsequently, \textit{A. Dudek} and \textit{A. Frieze} [ibid. 18, No. 1, Research Paper P48, 14 p., electronic only (2011; Zbl 1218.05174)] extended this result for any uniformity \(k\geq 4\), proving that if \(p\gg (\log n)/n^{k-1}\), then \(H^{(k)}_{n,p}\) contains a loose Hamilton cycle, provided that \(n\) is divisible by \(2(k-1)\). In this paper, we improve the divisibility requirement and show that in the above results it is enough to assume that \(n\) is a multiple of \(k-1\), which is best possible.
0 references
loose Hamilton cycles
0 references
random uniform hypergraphs
0 references