Breakthroughs Weekly — 20 September 2026
A 2004 conjecture on random regular graphs, unnoticed for nearly a year, draws expert praise once Quanta profiles the completed proof.
A proof of the Kim-Vu sandwich conjecture
arXiv · 23 Oct 2025 · Graph theory
Natalie Behague, Daniel Iľkovič and Richard Montgomery proved a 2004 conjecture of Jeong Han Kim and Van Vu, showing that every random d-regular graph can be sandwiched between two ordinary binomial random graphs with closely matched edge probabilities, extending earlier work that only covered much larger degrees. The proof builds the regular graph edge by edge using weighted coin flips that guarantee it contains a binomial graph, then reverses the process to complete the sandwich from the other side, fully analyzing a coupling technique earlier attempts had left incomplete. The preprint drew little notice outside specialists until Quanta Magazine profiled it on 18 September 2026, where Tel Aviv University’s Michael Krivelevich described finally seeing the finished proof as “some kind of relief.” Because binomial random graphs are far better understood than regular ones, the result lets researchers automatically transfer known properties across to regular graphs, a structure that shows up throughout network theory.