Mathematicians Finally Build the Long-Awaited Graph Sandwich
Mathematicians Build Long-Awaited Graph Sandwich
In 2004, Kim and Vu conjectured that any large enough random regular graph can be sandwiched between two random binomial graphs, letting hard properties transfer for free. Mathematicians had proved only pieces of it for two decades. Then in 2025, Richard Montgomery, Natalie Behague, and Daniel Iľkovič built the sandwich edge by edge, completing the proof and giving researchers a new tool for understanding complex networks.
The notion is so beautiful. What attracts me most is actually the beauty of it.
- omnicognate
Hilarious - a mathematical result that afaict has nothing whatsoever to do with AI, and 75% of the comments are about AI, including this one!
- mindleyhilner
Actual meat: https://arxiv.org/abs/2510.20765
- Sniffnoy
Wondering: if the process for the upper part of the sandwich is the complement of the process for the lower part, why was it so much more difficult? What would go wrong if you took one of the earlier lower-sandwich processes, and complemented it in a similar way? I have to assume it's something, but what?