Embedding the Erdos-Renyi hypergraph into the random regular hypergraph and Hamiltonicity

Abstrakt

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 infinity.

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 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) contains a tight Hamilton cycle.

Klíčová slova

• Random regular graph
• Random hypergraph
• Hamilton cycle
• Monotone graph property