{"id":620107,"date":"2026-09-18T15:20:15","date_gmt":"2026-09-18T15:20:15","guid":{"rendered":"https:\/\/www.newsbeep.com\/il\/620107\/"},"modified":"2026-09-18T15:20:15","modified_gmt":"2026-09-18T15:20:15","slug":"mathematicians-build-long-awaited-graph-sandwich","status":"publish","type":"post","link":"https:\/\/www.newsbeep.com\/il\/620107\/","title":{"rendered":"Mathematicians Build Long-Awaited Graph Sandwich"},"content":{"rendered":"

In 2004, two mathematicians hypothesized a powerful kind of sandwich.<\/p>\n

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 \u2014 a type that\u2019s ubiquitous in mathematics and computer science but difficult to analyze \u2014 by sandwiching it, in a mathematically rigorous way, between two simpler graphs.<\/p>\n

If researchers could prove the existence of such a sandwich, they wouldn\u2019t just be showing that the middle graph has one property of interest; they\u2019d be showing that it has all sorts of important properties. In doing so, they\u2019d 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\u2019d imagined.<\/p>\n

\u201cThe notion is so beautiful,\u201d said Pu Gao<\/a>, a mathematician at the University of Waterloo in Canada who has worked on the problem. \u201cWhat attracts me most is actually the beauty of it.\u201d<\/p>\n

In the past two decades, mathematicians made progress on the \u201csandwich conjecture,\u201d which says that so long as the graph you\u2019re 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\u2019s techniques to their limits, and completed the quest.<\/p>\n

Graphs of Different Flavors<\/p>\n

\"\" <\/p>\n

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 \u201crandom\u201d graph, in which vertices connect to other vertices at random. (The mathematicians Paul Erd\u0151s and Alfr\u00e9d R\u00e9nyi independently came up with a similar model at around the same time.)<\/p>\n

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.<\/p>\n

These graphs, known as random binomial graphs, turned out to provide a useful \u2014 if imperfect \u2014 way to represent networks. They were relatively easy to analyze, and mathematicians proved many interesting things about them. By the 1970s, for instance, they\u2019d discovered under what conditions a random binomial graph will contain a Hamiltonian cycle, a path that visits each vertex exactly once.<\/p>\n

\"\" <\/p>\n

But this isn\u2019t 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<\/a> than binomial graphs. And they\u2019re often much more accurate at modeling real-world networks.<\/p>\n

But because their edges form more constrained, interdependent patterns, they\u2019re 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.<\/p>\n

But what if you can approximate random regular graphs with random binomial graphs? If that\u2019s possible, then mathematicians can get many hard-to-prove properties of a regular graph from the matching binomial graph \u2014 for free.<\/p>\n

In the early 2000s, Jeong Han Kim<\/a>, then at Microsoft Research, and Van Ha Vu<\/a>, then at the University of California, San Diego, showed how to do this by making a graph sandwich<\/a>.<\/p>\n

\"\" <\/p>\n

The idea, loosely stated, was to find a single recipe \u2014 a random process \u2014 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.<\/p>\n

In the sandwich analogy, it\u2019s 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.<\/p>\n

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.<\/p>\n

First, you need a recipe that gives you a regular graph that contains a binomial graph. That is, the binomial graph\u2019s 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\u2019s sandwich.<\/p>\n","protected":false},"excerpt":{"rendered":"In 2004, two mathematicians hypothesized a powerful kind of sandwich. They were studying graphs, which are collections of…\n","protected":false},"author":2,"featured_media":620108,"comment_status":"","ping_status":"","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6],"tags":[85,46,125],"class_list":["post-620107","post","type-post","status-publish","format-standard","has-post-thumbnail","category-technology","tag-il","tag-israel","tag-technology"],"_links":{"self":[{"href":"https:\/\/www.newsbeep.com\/il\/wp-json\/wp\/v2\/posts\/620107","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.newsbeep.com\/il\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.newsbeep.com\/il\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.newsbeep.com\/il\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.newsbeep.com\/il\/wp-json\/wp\/v2\/comments?post=620107"}],"version-history":[{"count":0,"href":"https:\/\/www.newsbeep.com\/il\/wp-json\/wp\/v2\/posts\/620107\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.newsbeep.com\/il\/wp-json\/wp\/v2\/media\/620108"}],"wp:attachment":[{"href":"https:\/\/www.newsbeep.com\/il\/wp-json\/wp\/v2\/media?parent=620107"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.newsbeep.com\/il\/wp-json\/wp\/v2\/categories?post=620107"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.newsbeep.com\/il\/wp-json\/wp\/v2\/tags?post=620107"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}