Embedding the Erdős-Rényi Hypergraph into the Random Regular Hypergraph and Hamiltonicity

Abstract

We establish an inclusion relation between two uniform models of random $k$-graphs (for constant $k\ge 2$) on $n$ labeled vertices: ${\mathbb{G}}^{(k)}(n,m)$, the random $k$-graph with $m$ edges, and ${\mathbb{R}}^{(k)}(n,d)$, the random $d$-regular $k$-graph. We show that if $n\log n\ll m\ll n^k$ we can choose $d=d(n)\sim km/n$ and couple ${\mathbb{G}}^{(k)}(n,m)$ and ${\mathbb{R}}^{(k)}(n,d)$ so that the latter contains the former with probability tending to one as $n\to \infty$. This extends an earlier result of Kim and Vu about "sandwiching random graphs". In view of known threshold theorems on the existence of different types of Hamilton cycles in ${\mathbb{G}}^{(k)}(n,m)$, our result allows us to find conditions under which ${\mathbb{R}}^{(k)}(n,d)$ is Hamiltonian. In particular, for $k\ge 3$ we conclude that if $n^{k-2}\ll d\ll n^{k-1}$, then a.a.s. ${\mathbb{R}}^{(k)}(n,d)$ contains a tight Hamilton cycle.

Published online in Journal of Combinatorial Theory, Series B on 16 Sep 2016

Cited by in corpus (3)

• Entropy-based models to randomize real-world hypergraphs
• The Overlap Gap Property limits limit swapping in the QAOA
• Embedding theorems for random graphs with specified degrees