Kim and Vu conjectured that so long as your regular graph has a reasonable number of edges, you can almost always build this sandwich.
That’s no easy task, given that your recipe needs to create the binomial and regular graphs simultaneously, even though they usually get built using completely different random processes. Over the years, mathematicians proved that the bottom half of Kim and Vu’s sandwich existed, and they proved the upper half in some settings. “It was a sequence of ideas building upon one another,” said Michael Krivelevich, a mathematician at Tel Aviv University who has worked on the problem. Each step “requires a very good technique. It requires ingenuity.”
But the sandwich was not yet complete.
The Perfect Recipe
The proof of the conjecture would require a way to closely connect the bread and cheese of any sandwich.
In particular, the layers would be built up in tandem, guaranteeing that they would always fit together.
In 2023, three mathematicians — Richard Montgomery of the University of Warwick; Natalie Behague, his postdoctoral researcher at the time; and Daniel Iľkovič, his doctoral student — started to think about ways to build a random regular graph and a random binomial graph edge by edge, ensuring that at each step the regular graph would contain the binomial one. It’s a bit like making your sandwich out of tiny bits of shredded cheese, placing them on the bread one by one, rather than slapping a whole slice on at once.
Richard Montgomery helped craft a recipe for a mathematical sandwich that’s powerful but difficult to make.
Lisa Sauermann
To follow their recipe (which, the mathematicians note, is heavily adapted from a 2019 result by Gao and two colleagues), start with two sets of vertices without edges. One set will ultimately become your binomial graph, the other your regular graph.
Now build your binomial graph in the usual way. That is, choose a pair of vertices and flip a weighted coin. If your coin lands on heads, add an edge to the binomial graph. Add one to the regular graph as well.
If the coin lands on tails, don’t add the edge in the binomial graph. But you may or may not need to add an edge to the regular graph. After all, a regular graph is defined by the property that every vertex has the same number of edges. You need to make sure that all the required edges are there.
So when your coin lands on tails, ignore your binomial graph, but flip a second weighted coin to decide whether to add an edge to your regular graph. The weight of this second coin will change as you build up your graph. Behague, Iľkovič, and Montgomery came up with a clever way to estimate the weight of the coin as you add more edges to your graphs so that you’re guaranteed to get a truly regular graph. In addition, you also guarantee that your regular graph contains the binomial one, giving you the lower part of the sandwich.
To build the upper part, the mathematicians then reversed their entire process. They began with two graphs that contained every possible edge. They then removed edges one by one until they ended up with a regular graph and a binomial graph that contained it.
They had finished their sandwich. “The conjecture is in some way very natural. It was kind of annoying not to have it proven yet,” Krivelevich said. When he saw the trio’s new result, he was filled with “some kind of relief.”
Free Sides
With the sandwich conjecture resolved, mathematicians no longer have to prove every property of random regular graphs from scratch. They can now draw on the vast literature that’s been written about random binomial graphs and get all sorts of properties automatically.
That means they can rewrite scores of results about regular graphs in a single, streamlined proof. And new results are already starting to appear.
Moreover, the proof of this “meta-theorem,” as Gil Kalai of the Hebrew University of Jerusalem put it, offers a set of methods that “enriches our toolbox” and “sharpens our technical teeth.” Those methods might allow mathematicians to understand even more about the structure of networks than they originally set out to.
In the meantime, researchers hope to make even more complicated sandwiches, filled with alternating layers of binomial and regular graphs, or with other ingredients. In doing so, they’re continuing to explore the ways in which seemingly different random processes — one very constrained, the other not — are more similar than they look. “That sort of deep connection between the two,” Behague said, “seems almost too good to be true.” And yet it is.
