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