Natalie Behague (Dublin City University)
will speak on
On random regular graphs and the Kim-Vu Sandwich Conjecture
Time: 3:00PM
Date: Mon 13th April 2026
Location: E0.32 (beside Pi restaurant)
[map]
Abstract: The random regular graph G_d(n) is selected uniformly at random from all d-regular graphs on n vertices. This model is a lot harder to study than the Erdős-Renyi binomial random graph model G(n, p) as the probabilities of edges being present are not independent. Kim and Vu conjectured that when d ≫ log n it is possible to ‘sandwich’ the random regular graph G_d(n) between two Erdős-Renyi random graphs with similar edge density. A proof of this sandwich conjecture would unify many previous separate hard-won results.
Various authors have proved weaker versions of the sandwich conjecture with incrementally improved bounds on d — the previous state of the art was due to Gao, Isaev and McKay who proved the conjecture for d ≫ (log n)^4. I will sketch our new proof of the full conjecture.
This is joint work with Richard Montgomery and Daniel Il'kovič.
(This talk is part of the Probability series.)
PDF notice
Return to all seminars