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

2004 年，两位数学家假设了一种威力强大的三明治。他们正在研究图形，图形是点（称为顶点）和线（称为边）的集合。图表可以代表从社会群体到互联网再到大脑神经元的任何事物。数学家希望通过以数学上严格的方式将一种图形夹在两个更简单的图形之间来理解一种图形的属性（这种图形在数学和计算机科学中普遍存在，但难以分析）。如果研究人员能够证明这种三明治的存在，他们将不仅仅证明中间的图具有一个令人感兴趣的属性；他们会证明它具有各种重要的特性。在这样做的过程中，他们还将证明数学家喜欢研究的两个截然不同的随机过程以比他们想象的更深入、更优雅的方式联系在一起。 “这个想法太美妙了，”研究这个问题的加拿大滑铁卢大学数学家高普说。 “最吸引我的其实是它的美丽。”在过去的二十年里，数学家在“三明治猜想”上取得了进展，即只要你感兴趣的图足够大，你总能创造出所需的三明治。但没有人能够完全证明这一点。然后在 2025 年，三位数学家找到了一种将他们领域的技术推向极限的方法，并完成了任务。不同风味的图表 20 世纪 50 年代末，美国数学家埃德加·吉尔伯特 (Edgar Gilbert) 在贝尔实验室研究电话网络。为了更好地理解这些网络，他提出了一个简单的“随机”图模型，其中顶点随机连接到其他顶点。 （数学家 Paul Erdős 和 Alfréd Rényi 大约在同一时间独立提出了一个类似的模型。）要制作其中一个图，请从一组顶点开始。选择集合中的任意一对顶点，然后掷一枚（可能有偏差的）硬币。如果你得到了正面，就在它们之间画一条边；否则，继续。对图中的每对顶点重复此步骤。这些图被称为随机二项式图，结果提供了一种有用的（尽管不完美）表示网络的方法。它们相对容易分析，数学家证明了它们的许多有趣的事情。例如，到了 20 世纪 70 年代，他们发现了在什么条件下随机二项式图将包含哈密顿循环，即访问每个顶点一次的路径。但这并不是随机图的唯一类型。数学家也对所有顶点具有相同边数的随机图感到好奇。这些所谓的正则图比二项式图可以更好地理解随机结构。而且它们在对现实世界网络进行建模时通常更加准确。但由于它们的边缘形成了更受约束、相互依赖的模式，因此它们也更难分析。在回答了二项式图的哈密顿循环问题之后，数学家们又花了 20 年的时间才能够对正则图做同样的事情。但是，如果您可以用随机二项式图来近似随机正则图呢？如果可能的话，那么数学家就可以从匹配的二项式图中免费获得正则图的许多难以证明的属性。 2000 年代初期，当时在微软研究院工作的 Jeong Han Kim 和当时在加州大学圣地亚哥分校工作的 Van Ha Vu 展示了如何通过制作图形三明治来做到这一点。笼统地说，这个想法是找到一个单一的方法——一个随机过程——来同时构建二项式图和正则图。这个秘诀不仅需要生成正确类型的图表，而且这些图表还必须以正确的方式组合在一起。如果你能做到这一点，那么当你证明相对容易分析的二项式图的结果时，这些结果也适用于正则图。在三明治的类比中，这就像证明一片面包的情况，并知道这些结果也适用于中间的奶酪。但这些图表到底需要如何组合在一起呢？你必须想出一个食谱，将奶酪分别铺在每片面包上。首先，您需要一个方法来为您提供包含二项式图的正则图。也就是说，二项式图的边形成了构成正则图的边的子集。如果该二项式图具有在向其添加边时更有可能出现的任何属性，那么您的常规图也将具有该属性。这是 Kim 和 Vu 三明治的下半部分。