Loose Hamilton Cycles in Regular Hypergraphs

Abstract

We establish a relation between two uniform models of random $k$-graphs (for constant $k\ge 3$) on $n$ labeled vertices: $H(n,m)$, the random $k$-graph with exactly $m$ edges, and $H(n,d)$, the random $d$-regular $k$-graph. By extending to $k$-graphs the switching technique of McKay and Wormald, we show that, for some range of $d=d(n)$ and a constant $c>0$, if $m\sim cnd$, then one can couple $H(n,m)$ and $H(n,d)$ so that the latter contains the former with probability tending to one as $n\to \infty$. In view of known results on the existence of a loose Hamilton cycle in $H(n,m)$, we conclude that $H(n,d)$ contains a loose Hamilton cycle when $\log n=o(d)$ (or just $d\ge Clogn$, if $k=3$) and $d=o(n^{1/2})$.

17 pages, 1 figure

References in corpus (1)

• Approximate counting of regular hypergraphs

Cited by in corpus (2)

• Hamilton cycles in graphs and hypergraphs: an extremal perspective
• Embedding the Erdős-Rényi Hypergraph into the Random Regular Hypergraph and Hamiltonicity