数学家构造出期待已久的图三明治

引言

2004 年，两位数学家设想了一种威力强大的“三明治”。

他们研究的是图（graph），也就是由点（称为顶点）和线（称为边）组成的结构。图可以表示从社交圈到互联网再到大脑神经元的各种事物。数学中有一类图在数学和计算机科学中无处不在，却很难分析。数学家们希望用一种严格的方式，把它“夹”在两个更简单的图之间，从而理解它的性质。

如果研究者能证明这种“三明治”确实存在，那就不只是证明中间那个图具有某个性质，而是能证明它拥有一系列重要性质。同时，这也将表明数学家常研究的两种截然不同的随机过程，以比想象中更深刻、更优雅的方式联系在一起。

“这个概念太美了，”加拿大滑铁卢大学的数学家、曾研究过这一问题的 Pu Gao 说，“最吸引我的正是它的美。”

过去二十年里，数学家们在“三明治猜想”上不断取得进展。这个猜想断言：只要所研究的图足够大，就总能构造出所需的三明治。但始终没人能完整证明它。直到 2025 年，三位数学家把该领域的技术发挥到极致，终于完成了这项探索。

不同风味的图

20 世纪 50 年代末，美国数学家 Edgar Gilbert 在贝尔实验室研究电话网络。为了更好地理解这些网络，他提出了一个简单的“随机”图模型，其中顶点之间的连接是随机产生的。（大约同一时期，数学家 Paul Erdős 和 Alfréd Rényi 也独立提出了类似的模型。）

构造这样的图，先取一组顶点，任选其中一对，然后抛一枚（可能有偏的）硬币：正面就在两点之间连一条边，反面就跳过。对图中每一对顶点都重复这一步。

这类被称为随机二项图的网络，提供了一种实用但并不完美的网络表示方法。它们的分析相对容易，数学家们也据此证明了许多有趣的性质。例如，到 20 世纪 70 年代，人们已经发现随机二项图在何种条件下会包含哈密顿圈，即每条顶点恰好经过一次的闭合路径。

但这并非唯一的随机图类型。数学家们同样对“所有顶点度数相同”的随机图充满好奇。这种被称为正则图的结构，比二项图能更深刻地揭示随机结构，且往往更精准地模拟现实世界中的网络。

不过，由于正则图的边形成受约束更强、相互依赖更复杂的模式，分析起来要难得多。在回答了二项图的哈密顿圈问题后，数学家们又花了 20 年才实现对正则图的同等突破。

但如果能用随机二项图来近似随机正则图呢？若这可行，数学家就能直接从对应的二项图“免费”获取正则图许多难以证明的性质。

2000 年代初，当时在微软研究院工作的 金政汉（Jeong Han Kim）和当时在加州大学圣迭戈分校的 吴文哈（Van Ha Vu）通过构建“图三明治”实现了这一目标。

简单来说，其思路是找到一套统一的随机过程（食谱），同时生成一个二项图和一个正则图。这套方法不仅要能生成正确的图类型，还要确保这两个图以特定的方式契合。一旦达成，由于二项图相对容易分析，证明出的结果也同样适用于正则图。

用三明治作比喻，这就好比证明了其中一片面包的性质，从而推断出中间芝士层也具备相同的性质。

但那些图究竟该如何拼合？你需要一份食谱，把“奶酪”分别铺在每一片“面包”上。

首先，你得准备一份能生成规则图、且包含二项式图的食谱。也就是说，二项式图的边集必须是该规则图边集的子集。如果给二项式图增加边后，某个性质出现的概率会变大，那么你的规则图也必然具备这一性质。这就是 Kim 和 Vu 三明治的底部。

同理，你还需要一份能生成规则图、且被包含于二项式图的食谱。如果从这个更大的二项式图中移除边后，某些性质更容易显现，那么你的规则图也必须具备这些性质。这就是三明治的顶部。

Kim 和 Vu 曾猜想，只要规则图的边数处于合理范围内，几乎总能< a href="https://www.sciencedirect.com/science/article/pii/S0001870803003475">构建出这个三明治。

鉴于食谱必须在同一套流程中同时生成二项式图和规则图，而这两类图通常由截然不同的随机过程构建，这一任务绝非易事。多年来，数学家们已证明 Kim 和 Vu 三明治的底部存在，并在某些设定下证明了顶部也成立。特拉维夫大学的数学家 Michael Krivelevich 曾参与该问题的研究，他形容道：“这是一连串相互叠加的思路。每一步都需要极佳的技巧，需要灵巧的创意。”

但那时，三明治尚未完成。

完美食谱

要证明这个猜想，就需要找到一种方法，把三明治的“面包”和“奶酪”紧密地连接起来。

具体来说，就是要让这两“层”同步搭建，确保它们始终严丝合缝。

2023 年，三位数学家——华威大学的 Richard Montgomery、他当时的博士后研究员 Natalie Behague，以及他的博士生 Daniel Iľkovič——开始思考如何逐条边地同步构建随机正则图和随机二项图，并保证在每一步中，正则图都包含二项图。这就好比做三明治时不把整片奶酪一次盖上，而是把奶酪撕成碎屑，一片片铺在面包上。

按照他们的配方（数学家们指出，它大量改编自 Gao 及其同事在 2019 年的一项成果），先从两组没有边相连的顶点开始。一组最终将成为你的二项图，另一组则成为你的正则图。

接下来按常规方式构建二项图：随机选一对顶点，抛一枚带权重的硬币。如果正面朝上，就在二项图中添加一条边，同时在正则图中也添加一条。

如果反面朝上，二项图中就不添加这条边，但正则图中可能仍需要添加。毕竟，正则图的定义是每个顶点拥有相同数量的边，你得确保所有必需的边都到位。

当硬币背面朝上时，请忽略二项式图，转而抛一枚加权硬币，以决定是否在常规图中添加一条边。随着你构建图的过程推进，这枚硬币的权重会动态调整。Behague、Iľkovič 和 Montgomery 想出了一个巧妙的估算法：在添加更多边的过程中动态调整硬币权重，从而确保生成的是真正的常规图。此外，他们还保证该常规图包含对应的二项式图，从而构成了三明治的下半部分。 为了构建上半部分，数学家们将整个过程完全反转。他们从包含所有可能边的两个图开始，逐条删除边，直到最终得到一个常规图和一个包含它的二项式图。 至此，三明治完成了。“这个猜想从某种角度看非常自然，但一直没被证明确实让人有点恼火，”Krivelevich 说道。看到三人组的新成果时，他感到如释重负。

免费配菜

随着三明治猜想的解决，数学家们不再需要从零开始证明随机常规图的每一项性质。现在，他们可以直接引用关于随机二项式图的大量既有文献，自动获取各种性质。

这意味着他们可以用单一、精简的证明重写数十项关于常规图的结果。而且，新的成果已经开始涌现。

此外，正如耶路撒冷希伯来大学的 Gil Kalai 所言，这个“元定理”的证明提供了一系列“丰富我们工具箱”并“磨砺我们技术锋刃”的方法。这些方法或许能帮助数学家更深入地理解网络结构，超越最初的预期。

与此同时，研究人员正希望制作更复杂的三明治，用交替的二项式图和常规图作为夹心，或填入其他成分。在此过程中，他们继续探索那些看似不同的随机过程——一个受到严格约束，另一个则不然——之间比表面看起来更为相似的深层联系。“这两者之间的那种深层联系，”Behague 说，“简直好得令人难以置信。但事实如此。”