2004年，两位数学家提出了一个猜想。他们想研究一种图——由点和线组成的结构，可以表示社交网络、互联网，甚至大脑里的神经元。这种图在数学和计算机科学中无处不在，却极难分析。他们的办法是：用两块更简单的图，把它像三明治一样夹在中间。
如果这个三明治存在，研究者得到的就不只是中间那张图的一个性质，而是它的所有重要性质。同时，这也意味着两个看似完全不同的随机过程，之间存在一种比想象中更深、更优雅的联系。
“这个概念太美了，”加拿大滑铁卢大学的数学家Pu Gao说，她研究过这个问题。“最吸引我的，其实是它的美。”
两种图，两种难度
上世纪50年代末，美国数学家Edgar Gilbert在贝尔实验室研究电话网络。为了理解这些网络，他提出了一个“随机”图的简单模型：点与点之间随机连线。数学家Paul Erdős和Alfréd Rényi几乎在同一时间独立提出了类似模型。
造这种图的方法很直接：先取一组点，任选一对，抛一枚（可以是不均匀的）硬币。正面就画一条边，反面就跳过。对每一对点重复这一步。
这类图被称为随机二项图，是表示网络的一种有用——虽然不完美——的方式。它们相对容易分析，数学家证明了许多有趣的性质。比如到1970年代，他们已经搞清楚在什么条件下，随机二项图会包含一条哈密顿回路，也就是一条恰好经过每个点一次的路径。
但这并不是唯一的随机图。数学家还对另一种图感兴趣：所有点拥有相同数量的边。这种所谓的正则图，比二项图更能反映随机结构，在建模真实网络时往往也准确得多。
代价是：因为边的模式更受约束、彼此依赖，正则图分析起来难得多。二项图的哈密顿回路问题解决后，数学家又花了20年，才在正则图上得到同样的答案。
那么，能不能用随机二项图去近似随机正则图？如果可以，数学家就能从对应的二项图那里，免费拿到正则图许多难以证明的性质。
三明治的两片面包
2000年代初，当时在微软研究院的Jeong Han Kim和在加州大学圣迭戈分校的Van Ha Vu展示了怎么做这个三明治。
思路大致是：找到一套配方——一个随机过程——同时构造出一个二项图和一个正则图。这套配方不仅要生成正确的图，两张图还必须以恰到好处的方式嵌合。做到这一点，当你证明关于二项图的结果时，这些结果对正则图同样成立。
用三明治打比方：证明其中一片面包的性质，就等于知道了中间那层奶酪的性质。
但两张图到底要怎么嵌合？你需要一套配方，把奶酪分别铺在每一片面包上。
首先，你需要一套配方，得到一个包含二项图的正则图。也就是说，二项图的边是正则图边集的子集。如果这个二项图拥有某种“加边后更容易出现”的性质，那么正则图也会有这个性质。这是Kim和Vu三明治的下半部分。
类似地，你需要一套配方，得到一个被包含在二项图里的正则图。如果这个更大的二项图拥有某种“减边后更容易出现”的性质，那么正则图也必然拥有这些性质。这是三明治的上半部分。
Kim和Vu猜想：只要正则图的边数合理，你几乎总能造出这个三明治。
这并不容易，因为配方必须同时造出二项图和正则图，而它们通常是用完全不同的随机过程生成的。多年来，数学家证明了下半部分三明治的存在，也在某些情形下证明了上半部分。“这是一连串层层递进的想法，”特拉维夫大学的数学家Michael Krivelevich说，他研究过这个问题。每一步“都需要非常好的技巧，需要巧思”。
但三明治还没有完成。
完美的配方
证明这个猜想，需要一种把任何三明治的面包和奶酪紧密连接起来的方法。
具体来说，各层要同步构建，保证它们始终嵌合。
2023年，三位数学家——Richard Mont——
2025年，三位数学家找到了办法，把所在领域的技术推到了极限，完成了这项探索。
热门跟贴