Title: The sandwich conjecture of random regular graphs and more
The sandwich conjecture formulated in [Kim, Vu, Advances in Math., 2004] states that if d >> log n, then the random d-regular graph on n vertices R(n, d) can asymptotically almost surely be ”sandwiched” between G(n, p1) and G(n, p2) where probabilities p1 and p2 are both (1 + o(1))d/n. They proved this conjecture for the range log n << d < n1/3−o(1) with a defect in one side of sandwiching: a few edges from each vertex should be deleted from R(n, d) to guarantee the containment in G(n, p2). Recently, their one-sided containment result G(n, p1) ⊂ R(n, d) was extended by Dudek, Frieze, Rucinski and Sileikis to any log n << d = o(n).
We prove the sandwich conjecture (with perfect containments on both sides) for all values of d > n/ log n. For smaller values of d we establish non-tight containment R(n, d) ⊂ G(n, p) with p = ε(d/n) log n (for any constant ε > 0).
This is joint work with P. Gao and B.D. McKay
200 University Avenue West
Waterloo, ON N2L 3G1