Loose Hamilton Cycles in Random Uniform Hypergraphs

  • Andrzej Dudek
  • Alan Frieze

Abstract

In the random $k$-uniform hypergraph $H_{n,p;k}$ 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 adjacent edges intersects in a single vertex. We prove that if $p n^{k-1}/\log n$ tends to infinity with $n$ then $$\lim_{\substack{n\to \infty\\ 2(k-1) |n}}\Pr(H_{n,p;k}\text{ contains a loose Hamilton cycle})=1.$$ This is asymptotically best possible.

Published
2011-02-21
Article Number
P48