Optimal divisibility conditions for loose Hamilton cycles in random hypergraphs

Andrzej Dudek¹ ; Alan Frieze² ; Po-Shen Loh² ; Shelley Speiss¹

¹Western Michigan University
²Carnegie Mellon University

The electronic journal of combinatorics, Tome 19 (2012) no. 4

Résumé

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 Frieze 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, Dudek and Frieze extended this result for any uniformity $k\ge 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.

Détail

DOI : 10.37236/2523

Classification : 05C80, 05C65, 05C45, 05C38
Mots-clés : loose Hamilton cycles, random uniform hypergraphs