Mathematicians Build Long-Awaited Graph Sandwich
The proof of a decades-old conjecture has given researchers a new way to understand complex networks. The post Mathematicians Build Long-Awaited Graph Sandwich first appeared on Quanta Magazine.
A graph in mathematics is a collection of points called vertices (like dots) connected by lines called edges (like links). Graphs can model real-world networks such as social media connections, internet infrastructure, or even brain neurons. For example, a graph might represent a group of friends where each vertex is a person and each edge is a friendship. Mathematicians study graphs to understand their properties, such as whether there’s a path that visits every vertex exactly once, known as a Hamiltonian cycle. In 2004, two mathematicians hypothesized a way to analyze complex graphs by 'sandwiching' them between simpler ones, a method that could reveal hidden properties of the middle graph.
Mathematicians often study random graphs, where connections between vertices are determined by chance. The first type, called a random binomial graph, is built by flipping a coin for every pair of vertices. If the coin lands heads, an edge is added; otherwise, it isn’t. This model was introduced in the late 1950s by Edgar Gilbert at Bell Labs to study telephone networks. A second type, the regular graph, ensures every vertex has the same number of edges, making it more realistic for modeling real-world networks like power grids or social circles. However, regular graphs are harder to analyze because their edges follow stricter rules. Mathematicians wondered if they could use properties of random binomial graphs to infer properties of regular graphs.
In the early 2000s, mathematicians Jeong Han Kim and Van Ha Vu proposed a method to 'sandwich' a regular graph between two binomial graphs. The idea was to create a binomial graph that is a subset of the regular graph (bottom slice of bread) and another binomial graph that contains the regular graph (top slice of bread). If successful, any property proven for the binomial graphs would automatically apply to the regular graph in the middle. This 'sandwich conjecture' suggested that so long as the regular graph is large enough, such a sandwich could always be built. Over 20 years, mathematicians proved parts of the conjecture but couldn’t complete it until 2025.
In 2023, three mathematicians—Richard Montgomery, Natalie Behague, and Daniel Iľkovič—developed a step-by-step method to construct the sandwich. They started with two sets of vertices without edges: one for the binomial graph and one for the regular graph. They built the binomial graph by flipping a coin for each pair of vertices. If the coin landed heads, they added an edge to both graphs. If tails, they only added an edge to the regular graph using a second, carefully weighted coin flip. The weight of this second coin was adjusted dynamically to ensure the regular graph remained balanced (all vertices had the same number of edges). They then reversed the process to build the top half of the sandwich, removing edges until both graphs fit the required structure.
The proof of the sandwich conjecture allows mathematicians to leverage existing knowledge about binomial graphs to study regular graphs more efficiently. Instead of proving properties of regular graphs from scratch, they can now use results from the vast literature on binomial graphs, streamlining proofs and saving significant time. The proof also introduces new techniques that enrich the 'toolbox' of mathematicians, potentially enabling them to explore more complex networks. Researchers are now considering building even more intricate sandwiches with multiple layers, such as alternating binomial and regular graphs, to uncover deeper connections between different types of random processes.
