Optimal divisibility conditions for loose Hamilton cycles in random hypergraphs
type: Item
instance of: scholarly article
title: Optimal divisibility conditions for loose Hamilton cycles in random hypergraphs
zbMATH Open document ID: 1266.05152
author: Andrzej Dudek
author: Po-Shen Loh
author: Shelley Speiss
author: Alan Frieze
published in: The Electronic Journal of Combinatorics
publication date: 2013-06-07T00:00:00Z
full work available at URL: v19i4p44
review text: 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.
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 6171827
zbMATH Keywords: loose Hamilton cycles
zbMATH Keywords: random uniform hypergraphs
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 6171827