Tutte Colloquium - Mikhail Isaev

Title: The sandwich conjecture of random regular graphs and more

Abstract:

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, p₁) and G(n, p₂) where probabilities p₁ and p₂ are both (1 + o(1))d/n. They proved this conjecture for the range log n << d < n^1/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, p₂). Recently, their one-sided containment result G(n, p₁) ⊂ 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