数学家成功证明图三明治猜想，将难解的正则图夹在易解的二项图之间，为复杂网络研究开辟了全新路径。
在现实生活中，社交网络、互联网乃至大脑中的神经元连接，都可以用由节点和边组成的图来表示。为了理解这些复杂的网络结构，数学家们长期依赖随机图模型。1950年代末，贝尔实验室的Edgar Gilbert以及Paul Erdős和Alfréd Rényi分别独立提出了二项随机图模型。这种模型的构建方式非常简单：在每对节点之间抛掷一枚硬币，如果正面朝上就画一条边，反之则不画。由于这种结构相对容易分析，数学家们在1970年代就成功掌握了其许多关键性质，例如判断图何时包含经过每个节点恰好一次的路径。
然而，现实世界中的许多网络往往具有更严格的规律，例如每个节点的连接数量完全相同，这被称为正则图。正则图能更真实地反映真实网络，但因为其边与边之间存在复杂的依赖关系，数学分析变得极其困难。数学家们花了额外20年时间，才在正则图上推导出了类似的结论。
既然二项图容易分析，而正则图难以破解，能否用二项图来逼近正则图？2004年，当时任职于微软研究院的Jeong Han Kim和加州大学圣迭戈分校的Van Ha Vu提出了著名的三明治猜想。他们的直觉非常巧妙：如果能找到一种随机过程，把难以分析的正则图夹在两个容易分析的二项图之间，就像在两片面包之间夹上一片奶酪，那么二项图所具备的优良性质，就能自动赋予夹在中间的正则图。
要造出这个数学三明治并不容易。下层面包需要一个包含二项图的正则图，只要二项图具备某种随边数增加而出现的性质，正则图就必然具备；上层面包则需要一个包含正则图的更大二项图。20多年来，包括滑铁卢大学的Pu Gao和特拉维夫大学的Michael Krivelevich在内的多位数学家不断推进这一猜想，但始终未能完成完整的证明。
转机出现在2023年。华威大学的Richard Montgomery与团队成员Natalie Behague和Daniel Iľkovič提出了全新突破口。他们不再试图一次性铺设整片奶酪，而是像撒碎奶酪一样，逐条边地构建图结构。通过巧妙调整抛硬币的概率，他们不仅保证了生成的正则图完全包含下层的二项图，随后又通过逆向删除边的过程成功构建了上层面包。
2025年，这项长期悬而未决的猜想终于得到完整证明。耶路撒冷希伯来大学的Gil Kalai将其称为一项元定理。这一成果不仅让数学家无需再从零开始证明正则图的繁杂性质，更将两套原本看似独立的随机过程紧密连接在一起，为研究复杂网络结构提供了威力强大的新工具。
原文：https://www.quantamagazine.org/mathematicians-build-long-awaited-graph-sandwich-20260918/