Embedding the Erdos-Renyi Hypergraph into the Random Regular Hypergraph and Hamiltonicity

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