A Proof of the Kim-Vu Sandwich Conjecture

Random regular graphs (Gd(n)) are central objects in the study of random graphs, yet the lack of independence between edges makes them significantly more difficult to analyze than the standard binomial random graph (G(n,p)). To bridge this gap, Kim and Vu (2004) formulated the "Sandwich Conjecture", proposing that for degrees d≫logn, a random d-regular graph can be coupled with two binomial random graphs such that G(n,p_∗)⊆Gd(n)⊆G(n,p^∗) with high probability, where p_∗ and p^∗ are (1+- \epsilon) d/n. Such a coupling allows certain properties of random regular graphs to be directly inferred from the well-understood binomial model.