A proof of the Kim-Vu sandwich conjecture

The random regular graph G_d(n) is selected uniformly at random from all d-regular graphs on a fixed set of n vertices. Compared to the binomial random graph G(n,p), the lack of independence between the appearance of the edges has made the random regular graph in practice usually much harder to study. In 2004, Kim and Vu conjectured that when d is much larger than log n it is possible to 'sandwich' the random regular graph G_d(n) between two binomial random graphs with a similar edge density, allowing properties of the random regular graph to be inferred from those of the binomial random graph. I will discuss a recent proof of this conjecture, building on work of Gao, Isaev and McKay who proved the conjecture for d at least (log n)^4.

 

This is joint work with Natalie Behague and Daniel Il'kovic.