A 20-year-old conjecture in random graph theory has finally been proved. Natalie Behague, Daniel Iľkovič, and Richard Montgomery proved the Kim-Vu sandwich conjecture, which goes back to 2004.
The interesting part is not just that another conjecture got crossed off the list. The result gives mathematicians a way to take a lot of what we already know about random binomial graphs and carry it over to random regular graphs, which are considerably more annoying to work with.
The proof was actually completed in 2025, but Quanta just published a good account of why people care about it. Instead of proving a bunch of results all over again for random regular graphs, this theorem can sometimes let you bring the old results with you.
That could save mathematicians a lot of unnecessary suffering.
Original paper: A Proof of the Kim-Vu Sandwich Conjecture
More from Dogmathic
For more math news, explanations, proofs, examples, and commentary, check out Dogmathic Math Notes and the latest Dogmathic videos. You can also grab free PDFs and LaTeX resources or sign up for occasional email updates when something worth sharing gets published.
Leave a Reply