随机图会导致三角形（右）、哈密顿循环（中）或其他感兴趣的属性吗？
Quanta 杂志的 Olena Shmahalo
当数学家Jeff Kahn和Gil Kalai在 2006 年首次提出他们的“期望阈值”猜想时，他们自己并不相信。他们的主张——对称为随机图的数学对象的广泛断言——似乎太强大、太包罗万象、太大胆以至于不可能是真的。感觉更像是一厢情愿，而不是数学真理的反映。即便如此，没有人可以证明它是错误的，它很快成为该领域最重要的开放问题之一。
现在，15 年多过去了，斯坦福大学的一对年轻数学家完成了卡恩和卡莱认为不可能完成的事情：在几周前发布在网上的一份令人惊讶的短预印本中， Jinyoung Park和Huy Tuan Pham提供了完整的证明的猜想。
“它非常简单和巧妙，”卡莱说。 “这太棒了。太棒了。”
结果自动证明了数百个更具体的陈述，每一个陈述都很难单独证明——而且它对我们更广泛地理解随机图和数学集有更深层次的影响。
“我认为他们的证明很神奇，”斯坦福大学的数学家兼 Pham 的博士顾问Jacob Fox说。 “这将成为该领域未来的重要组成部分。”
冻结图表
卡恩-卡莱猜想非常广泛——它是用集合及其元素的抽象语言写成的——但可以通过考虑一个简单的案例来理解。首先，想象一个图：一组由线或边连接的点或顶点。要制作随机图，请取一枚有偏差的硬币——一个以 1%、30% 或 0 到 100 之间的任何其他百分比落在正面的硬币——并针对给定的一对顶点翻转一次。如果硬币落在正面，将这些顶点与边连接起来；如果硬币落在尾巴上，不要。对每对可能的顶点重复此过程。
斯坦福大学的数学家 Jinyoung Park “能感受到这个猜想的美妙和力量，”她说。 “但我从没想过我会证明这一点。”
罗德·瑟西
数学家想知道这样的图何时可能具有某种有趣的结构。也许它会包含一个三角形。或者它可能会有一个哈密顿循环，即一条通过每个顶点恰好一次的边链。可以考虑任何属性，只要它是“增加的”——也就是说，如果向已经包含该属性的图添加更多边不会破坏该属性。
如果硬币正面朝上的概率很低，则边缘将很少，并且不太可能出现哈密顿循环等性质。但如果你调高概率，就会发生一些奇怪的事情。每个属性都有一个所谓的阈值：结构出现的概率，通常非常突然。
就像当温度降至零摄氏度以下时会形成冰晶一样，随着更多的边被添加到图表中，特定属性的出现突然变得极有可能。例如，当边以小于 log( N )/ N的概率添加到具有N个顶点的随机图中时，该图不太可能包含哈密顿循环。但是当这个概率被调整为比 log( N )/ N大一点时，哈密顿循环变得极有可能。
数学家想要确定各种感兴趣属性的阈值。 “阈值可能是你试图理解的最基本的东西，”福克斯说。 “我看着一个随机的物体；它有我感兴趣的财产吗？”然而，虽然已经为哈密顿循环和其他一些特定结构计算了阈值，但在大多数情况下，仍然很难确定一个精确的阈值，甚至是对一个阈值的良好估计。
因此，数学家通常依赖于一种更简单的计算，即为阈值提供最小可能值或下限的计算。这个“预期阈值”基本上是通过加权平均来计算的。 “这个期望阈值的好处是它非常容易计算，”加州理工学院的数学家大卫康伦说。 “一般来说，你几乎可以用两行来计算这个期望阈值。”
但平均值可能会产生误导。例如，对于哈密顿循环，期望阈值为 1/ N ，它比 log( N )/ N的真实值低 log( N ) 倍。
耶路撒冷希伯来大学的 Gil Kalai。
Quanta 杂志的 Daniel Vaaknin
2006 年，卡恩和卡莱认为这实际上是最坏的情况。他们的同名猜想指出，期望阈值和真实阈值之间的差距永远不会大于对数因子。根据 Conlon 的说法，这个猜想“本质上是随机图中的中心问题，并给出了一个一般性的答案。”
但这只是一个简单的案例。这个猜想不仅仅适用于随机图。如果为真，它适用于随机数序列、称为超图的图的概括，甚至适用于更广泛类型的系统。那是因为卡恩和卡莱是用抽象集合来写他们的声明的。随机图构成了一种特定情况——随机图可以被认为是所有可能边集的随机子集——但还有许多其他对象落入猜想的范围内。 “奇怪的是，当你处理图表时，在这种情况下证明它会非常困难，”Conlon 说。 “但不知何故，跳到这个抽象的环境揭示了这件事的核心。”
正是这种普遍性使该声明显得如此令人难以置信。 “这是一个非常勇敢的猜想，”加州大学圣地亚哥分校的理论计算机科学家Shachar Lovett说。一方面，它会立即简化组合学方面的巨大工作——尝试计算不同属性的阈值。卡内基梅隆大学的数学家Alan Frieze说：“看似证明需要非常长且复杂的问题突然消失了。” “证明只是这个[猜想]的微不足道的应用。”
这么多看似无关的问题可以通过如此广泛的猜想来解决，这对许多数学家来说是一种牵强。 “老实说，这似乎完全疯了，”康伦说。在设计出他们的猜想后，卡恩和卡莱并没有试图证明这一点。他们努力寻找一个反例。他们可以探索的环境太多了，他们认为最终一定会偶然发现一个。
但事实证明，“故事的发展方式与他们预期的完全不同”，Kalai 说。
向日葵之路
最终导致卡恩-卡莱猜想的新证明的方法始于对一个看似无关的问题的突破。在许多方面，故事都始于向日葵猜想，这是数学家 Paul Erdős 和 Richard Rado 在 1960 年提出的一个问题。向日葵猜想考虑是否可以以类似于向日葵花瓣的方式构建集合。
2019 年，洛维特加入了一个非常接近完全解决向日葵问题的团队。当时，这项工作似乎与卡恩-卡莱猜想完全不同，后者涉及概率的考虑。 “我没有看到与我们的猜想有任何联系，”卡莱说。洛维特也没有，他说“我们不知道这些[其他]问题。我们关心向日葵。”
Huy Tuan Pham。
在三月份的一个不眠之夜中，他们想出了如何使证明发挥作用。
与分数期望阈值不同，正常期望阈值与散布无关。传播“给你一个起点。如果你去原始的非分数猜想，那个起点就会消失，”卡恩说。 “所以看起来很艰难。”
“所以你会怎么做？”范说。 “在这种情况下，我们改变了观点。”
特别是，他们根据称为封面的数学对象来考虑问题。封面是集合的集合，其中每个具有特定属性的对象都包含其中一个集合。例如，所有哈密顿循环的一种可能覆盖是所有边的集合。每个哈密顿循环都将包含这些边之一。
Park 和 Pham 改写了 Kahn-Kalai 猜想，让他们可以利用封面。最初的猜想对加权硬币正面朝上的概率进行了限制，以保证随机图或集合包含某些属性。特别是，它表示概率必须至少是属性的期望阈值乘以对数因子。 Park 和 Pham 扭转了这一局面：如果这样的属性不太可能出现，那么分配给加权硬币的概率低于预期阈值乘以对数因子。
这就是覆盖的用武之地：当可以为结构的子集（如哈密顿循环的集合）构建小覆盖时，这意味着该子集对期望阈值的贡献很小。 （请记住，期望阈值是通过对给定类型的所有可能结构进行加权平均来计算的。）因此，Park 和 Pham 现在需要证明的是，如果随机集不太可能包含一个目标结构，则必须存在所有此类目标结构的小覆盖。他们的大部分证明都致力于构建那个小封面。
他们通过使用与先前结果中使用的类似的逐个采样过程来做到这一点，同时还引入了 Fox 所说的“非常聪明的计数论点”。在三月的不眠之夜之后的一周，他们将优雅的六页论文发布到了网上。
“他们的证明非常简单。他们采用了我们开发的基本想法和其他论文中的想法，并对其进行了修改，”洛维特说。 “有了这个新的转折，一切都变得更加容易了。”
弗里兹同意了。 “我无法解释，但令人惊讶的是，这是真的，”他说。
就像分数结果一样，卡恩-卡莱猜想现在被证明是正确的，它自动暗示了相关猜想的聚宝盆。但更重要的是，“这是一种强大的证明技术，可能会带来新事物，”普林斯顿大学的数学家Noga Alon说。 “他们必须以正确的方式去做。”
Park 和 Pham 现在已经开始将他们的方法应用于其他问题。他们对更准确地了解期望阈值和实际阈值之间的差距特别感兴趣。通过证明卡恩-卡莱猜想，他们证明了这个差距最多是一个对数因子——但有时这个差距更小，甚至不存在。目前，没有更广泛的机制来分类这些场景中的每一个何时可能是真实的。数学家必须逐案解决。现在，“我们认为，通过我们拥有的这种有效技术，我们有望更加精确地确定这些阈值，”Pham 说。
他们的证明也可能产生其他后果。 “卡恩-卡莱猜想根本不是故事的结局，”朴说。