数学家构建期待已久的Graph Sandwich

# 数学家构建期待已久的图"三明治" | Quanta Magazine 来源：https://www.quantamagazine.org/mathematicians-build-long-awaited-graph-sandwich-20260918/ 2004年，两位数学家提出了一种强有力的"三明治"构想。 他们当时正在研究图——由点（称为顶点）和线（称为边）构成的集合。图可以表示从社交网络到互联网乃至大脑神经元的任何事物。这两位数学家希望通过一种数学上严谨的方式，将一种图——这种图在数学和计算机科学中无处不在但难以分析——"夹"在两个更简单的图之间，从而理解其性质。 如果研究者能证明这种"三明治"的存在，他们不仅会证明中间图具有一种有趣的性质，更会证明它具有各种重要性质。在此过程中，他们还将展示数学家喜欢研究的两种截然不同的随机过程，实际上以比想象中更深邃、更优雅的方式相互关联。 "这个概念太美妙了，"加拿大滑铁卢大学数学家高璞（https://www.math.uwaterloo.ca/~p3gao/）说，他曾研究过这个问题。"最吸引我的其实是它的美感。" 过去二十年间，数学家在"三明治猜想"上取得了进展——该猜想指出，只要所研究的图足够大，总能构建出所需的"三明治"。但无人能完全证明它。直到2025年，三位数学家找到了将领域内技术推向极限的方法，最终完成了这一探索。 ## **不同类型的图** 20世纪50年代末，美国数学家埃德加·吉尔伯特在贝尔实验室研究电话网络。为了更好地理解这些网络，他提出了一个简单的"随机"图模型，其中顶点随机连接其他顶点。（数学家保罗·埃尔德什和阿尔弗雷德·雷尼几乎在同一时期独立提出了类似模型。） 要构建这种图，首先需要一组顶点。从中任选一对顶点，抛掷一枚（可能不均匀的）硬币。若正面朝上，则在两点间画一条边；否则跳过。对图中每一对顶点重复此步骤。 这类被称为随机二项图的图，后来被证明是一种有用（虽不完美）的网络表示方式。它们相对容易分析，数学家证明了许多有趣的性质。例如，到20世纪70年代，他们已发现随机二项图在何种条件下会包含哈密顿回路——一条恰好访问每个顶点一次的路径。 但这并非随机图的唯一类型。数学家也对所有顶点具有相同边数的随机图感兴趣。这类所谓的正则图能比二项图更好地理解随机结构（https://www.quantamagazine.org/new-proof-settles-decades-old-bet-about-connected-networks-20250418/），并且在模拟现实世界网络时通常更为准确。 但由于它们的边形成了更受限、相互依存的模式，分析难度也大得多。在二项图哈密顿回路问题解决后，又过了20年，数学家才得以对正则图完成同样的证明。 但如果能用随机二项图近似随机正则图呢？如果可行，数学家就能从匹配的二项图中"免费"获得正则图许多难以证明的性质。 21世纪初，时任微软研究院的金正韩（https://www.kias.re.kr/kias/people/faculty/viewMember.do?memberId=10460&trget=listFaculty&menuNo=408002）与加州大学圣迭戈分校的范河武（https://www.scifac.hku.hk/people/vu-van-ha）展示了如何通过构建图"三明治"（https://www.sciencedirect.com/science/article/pii/S0001870803003475）实现这一目标。 简单来说，其核心思想是找到一个统一的方案——一个随机过程——同时生成一个二项图和一个正则图。这个方案不仅要生成正确类型的图，还必须让这些图以恰当方式契合。如果做到这一点，那么当证明了相对容易分析的二项图的性质时，这些结论同样适用于正则图。 在"三明治"的比喻中，这就像证明了其中一片面包的性质，就知道这些结论同样适用于中间的奶酪。 但这些图究竟需要如何契合呢？你需要设计一个方案，分别将奶酪铺在每片面包上。 首先，你需要一个方案，能产生一个**包含**二项图的正则图。也就是说，二项图的边是构成正则图的边集的一个子集。如果该二项图具有某种在**添加**边时更可能出现的性质，那么你的正则图也会具有该性质。这就是金正韩和范河武"三明治"的下半部分。