Optimal Divisibility Conditions for Loose Hamilton Cycles in Random Hypergraphs

  • Andrzej Dudek
  • Alan Frieze
  • Po-Shen Loh
  • Shelley Speiss
Keywords: loose Hamilton cycles, random uniform hypergraphs

Abstract

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.

Published
2012-12-13
Article Number
P44