Mathematicians Build Long-Awaited Graph Sandwich

This reports a long-standing conjecture in random-graph theory about “sandwiching” a random regular graph between two random binomial graphs so that one binomial graph is a subgraph of the regular graph and the regular graph is a subgraph of a larger binomial graph. Random binomial graphs are easy to analyze because each potential edge appears independently with a fixed probability, while random regular graphs require every vertex to have the same degree and are far harder. Kim and Vu conjectured in the early 2000s that for sufficiently large graphs such a sandwich always exists, which would let researchers transfer many properties proven for binomial graphs directly to regular graphs. Over two decades mathematicians proved partial results but lacked a full proof of the conjecture.

Richard Montgomery, Natalie Behague and Daniel Iľkovič completed the proof by devising a coupled, edge-by-edge construction that simultaneously builds a binomial graph and a regular graph with dynamically adjusted edge probabilities. Their process - drawing on techniques from a 2019 result by Pu Gao and collaborators - guarantees containment in the forward direction and then is reversed to produce the upper containment, completing the sandwich. The result functions as a meta-theorem: it streamlines and unifies many previous proofs about random regular graphs, supplies new technical tools, and opens the way to more elaborate layered constructions linking different random processes.