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 1) and G (n , p 2) where p 1 and p 2 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 1) perfectly, but is not completely contained in G (n , p 2) . The embedding G (n , p 1) ⊆ 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 / log n . 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. [ABSTRACT FROM AUTHOR]