Loose Hamilton Cycles in Random 3-Uniform Hypergraphs

  • Alan Frieze

Abstract

In the random hypergraph $H=H_{n,p;3}$ each possible triple appears independently with probability $p$. A loose Hamilton cycle can be described as a sequence of edges $\{x_i,y_i,x_{i+1}\}$ for $i=1,2,\ldots,n/2$ where $x_1,x_2,\ldots,x_{n/2},y_1,y_2,\ldots,y_{n/2}$ are all distinct. We prove that there exists an absolute constant $K>0$ such that if $p\geq {K\log n\over n^2}$ then $$\lim_{\textstyle{n\to \infty\atop 4|n}}\Pr(H_{n,p;3}\ contains\ a\ loose\ Hamilton\ cycle)=1.$$

Published
2010-05-25
Article Number
N28