Sandwiching dense random regular graphs between binomial random graphs

Kim and Vu made the following conjecture (Advances in Mathematics, 2004): if d≫ log n, then the random d-regular graph G(n, d) can asymptotically almost surely be “sandwiched” between G(n, p₁) and G(n, p₂) where p₁ and p₂ are both (1 + o(1)) d/ n. They proved this conjecture for log n≪ d⩾ n^1/3-o(1), with a defect in the sandwiching: G(n, d) contains G(n, p₁) perfectly, but is not completely contained in G(n, p₂). The embedding G(n, p₁) ⊆ G(n, d) was improved by Dudek, Frieze, Ruciński and Šileikis to d= o(n). In this paper, we prove Kim–Vu’s sandwich conjecture, with perfect containment on both sides, for all d where min{d,n-d}≫n/logn. The sandwich theorem allows translation of many results from G(n, p) to G(n, d) such as Hamiltonicity, the chromatic number, the diameter, etc. It also allows translation of threshold functions of phase transitions from G(n, p) to bond percolation of G(n, d). In addition to sandwiching regular graphs, our results cover graphs whose degrees are asymptotically equal. The proofs rely on estimates for the probability of small subgraph appearances in a random factor of a pseudorandom graph, which is of independent interest.