수학자들이 20년 묵은 '그래프 샌드위치' 추측을 증명하다

Home Mathematicians Build Long-Awaited Graph Sandwich Comment Save Article Read Later Share Facebook Copied! Copy link Email Pocket Reddit Ycombinator Comment Comments Save Article Read Later Read Later graph theory Mathematicians Build Long-Awaited Graph Sandwich By Paulina Rowińska September 18, 2026 The proof of a decades-old conjecture has given researchers a new way to understand complex networks. Comment Save Article Read Later Introduction In 2004, two mathematicians hypothesized a powerful kind of sandwich. They were studying graphs, which are collections of points (called vertices) and lines (called edges). Graphs might represent anything from social groups to the internet to neurons in the brain. The mathematicians hoped to understand properties of one type of graph — a type that’s ubiquitous in mathematics and computer science but difficult to analyze — by sandwiching it, in a mathematically rigorous way, between two simpler graphs. If researchers could prove the existence of such a sandwich, they wouldn’t just be showing that the middle graph has one property of interest; they’d be showing that it has all sorts of important properties. In doing so, they’d also be demonstrating that two very different random processes that mathematicians like to study are connected in a deeper and more elegant way than they’d imagined. “The notion is so beautiful,” said Pu Gao , a mathematician at the University of Waterloo in Canada who has worked on the problem. “What attracts me most is actually the beauty of it.” In the past two decades, mathematicians made progress on the “sandwich conjecture,” which says that so long as the graph you’re interested in is large enough, you can always create the needed sandwich. But no one could prove it in full. Then in 2025, three mathematicians found a way to push their field’s techniques to their limits, and completed the quest. Graphs of Different Flavors In the late 1950s, the American mathematician Edgar Gilbert was studying telephone networks at Bell Labs. To better understand those networks, he came up with a simple model of a “random” graph, in which vertices connect to other vertices at random. (The mathematicians Paul Erdős and Alfréd Rényi independently came up with a similar model at around the same time.) To make one of these graphs, start with a set of vertices. Choose any pair of vertices in your set, then flip a (potentially biased) coin. If you get heads, draw an edge between them; otherwise, move on. Repeat this step for every pair of vertices in the graph. These graphs, known as random binomial graphs, turned out to provide a useful — if imperfect — way to represent networks. They were relatively easy to analyze, and mathematicians proved many interesting things about them. By the 1970s, for instance, they’d discovered under what conditions a random binomial graph will contain a Hamiltonian cycle, a path that visits each vertex exactly once. But this isn’t the only type of random graph. Mathematicians were also curious about random graphs in which all vertices have the same number of edges. These so-called regular graphs provide a better understanding of random structure than binomial graphs. And they’re often much more accurate at modeling real-world networks. But because their edges form more constrained, interdependent patterns, they’re also much harder to analyze. It took an additional 20 years of work after the question about Hamiltonian cycles was answered for binomial graphs before mathematicians could do the same for regular graphs. But what if you can approximate random regular graphs with random binomial graphs? If that’s possible, then mathematicians can get many hard-to-prove properties of a regular graph from the matching binomial graph — for free. In the early 2000s, Jeong Han Kim , then at Microsoft Research, and Van Ha Vu , then at the University of California, San Diego, showed how to do this by making a graph sandwich . The idea, loosely stated, was to find a single recipe — a random process — to build a binomial graph and a regular graph at the same time. Not only does this recipe need to generate the right kinds of graphs, but those graphs must also fit together in just the right way. If you can do this, then when you prove results about the binomial graph, which is relatively easy to analyze, those results will also hold for the regular graph. In the sandwich analogy, it’s like proving things about one of the slices of bread and knowing that those results will also hold true for the cheese in the middle. But how do those graphs need to fit together, exactly? You have to come up with a recipe that layers the cheese on each slice of bread separately. First, you need a recipe that gives you a regular graph that contains a binomial graph. That is, the binomial graph’s edges form a subset of the edges that make up the regular graph. If that binomial graph has any property that is more likely to appear when you add edges to it, then your regular graph will also have that property. This is the bottom half of Kim and Vu’s sandwich. Similarly, you need a recipe that gives you a regular graph that is contained within a binomial graph. If this bigger binomial graph has properties that are more likely to appear when you remove edges from it, then your regular graph must also have these properties. This is the top half of your sandwich. 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. 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