图论中的一个非常大的小飞跃

15 月 XNUMX 日，有趣的研讨会公告在组合学（计数的数学研究）领域引起轰动。 三位合作者计划在第二天进行协调会谈。 朱利安·萨哈斯拉布德 将在英国剑桥向数学家发表讲话，同时 西蒙·格里菲思 将在里约热内卢分享新闻并 马塞洛·坎波斯 在圣保罗。 这三场演讲都有相同的标题和含糊不清的两句摘要，引用“Erdős 一个老问题的最新进展”。 1996 年去世的匈牙利数学家 Paul Erdős 提出 数百个问题 在他的职业生涯中，组合学家很快就猜出了三人组计划讨论的具体问题。 关于一个叫做拉姆齐数的谣言四处流传，这是所有数学中最难计算的数量之一。

Ramsey 数催生了一门名为 Ramsey 理论的学科，该学科在大量系统中寻找不可避免的模式。

例如，假设您尝试将所有整数分布在多个桶中，并且您希望避免在任何桶中放置均匀间隔的数字序列。 Ramsey 理论表明你会失败（除非你有无限多的桶）。 该理论可以应用于大多数您可以计算的事物。 它的核心教训是“你不能创造一个完全混乱的系统，”瑞士苏黎世联邦理工学院的数学家 Benny Sudakov 说。

Ramsey 数量化了在不可避免地出现特定模式之前范例示例必须有多大。 但是，尽管它处于中心地位，但除了 最简单的例子. 他们所能做的最好的事情就是找到可能的限制（或界限）。 即便如此，近一个世纪前由 Erdős 和一位合作者首先建立的上限几乎没有动摇。

然后，在 15 月 XNUMX 日的研讨会上，以及在当晚晚些时候发表的一篇论文中，研究人员宣布他们已经将拉姆齐数的上限提高了指数数量。

“我被打倒了，”说 尤瓦尔威德森，特拉维夫大学的数学家，听说了这个新结果。 “我真的颤抖了半小时到一个小时。”

党的路线

Ramsey 理论最常提出有关整数或图形的问题。 在这种情况下，图形指的是称为节点的点的集合，这些点由称为边的线连接，这些线可以具有长度或（如在拉姆齐数的情况下）颜色等属性。

完整的图既复杂又简单——每个节点都连接到其他每个节点。 Ramsey 数描述了一个完整的图必须包含多少个节点才能强制具有特定的结构。 假设一个完整图的边被分配了两种颜色之一：红色或蓝色。 并假设您尝试以一种避免将一组具有相同颜色边缘的节点连接起来的方式为边缘着色。 1930 年，弗兰克·拉姆齐 (Frank Ramsey) 证明，如果图足够大，就不可避免地会产生数学家所说的单色集团——一组公共边要么全是红色，要么全是蓝色的节点。

在被迫出现单色集团之前，图表究竟必须有多大？ 答案取决于集团的规模。 Ramsey 表明存在一个数字，现在称为 Ramsey 数，表示必须存在给定大小的单色团的最小节点数，无论边缘如何着色。

但拉姆齐数的大小很难确定。 1935 年，即 Ramsey 证明它存在的五年后，Erdős 和 George Szekeres 提供了一个新的、更严格的上限，说明给定规模的集团的 Ramsey 数有多大。 但从那以后，数学家几乎无法改进 Erdős 和 Szekeres 的计算。

为了更好地理解这意味着什么，请考虑一个经典示例，其中节点代表派对上的客人。 如果他们以前见过面，则将任意两位客人之间的边缘涂成红色，如果他们没有见过面，则将其涂成蓝色。 你可以选择任何你喜欢的小圈子规模——邀请足够多的人参加聚会，你不可避免地要么邀请一群彼此都认识的人（这个词有多种含义的小圈子），要么邀请一群人以前从未见过面。

“你可以在图表中拥有的最简单的东西是单色集团，”说 玛丽亚·楚德诺夫斯基（Maria Chudnovsky），普林斯顿大学数学家。 “令人惊讶的是，在每个巨大的图表中你都能找到其中的一个大图表。 完全不清楚。”

前几个拉姆齐数计算起来相对简单。 假设您想知道必须不可避免地包含大小为二的团或数学家 R(2) 的最小图的大小。 由于具有两个节点的完整图只是由一条边连接的两个节点，并且该边必须是红色或蓝色，因此 R(2) 为 2。更一般地，R(k), 或拉姆齐数 k, 是图无法避免包含大小的团的最小节点数 k.

不难证明大小为 3 的集团或 R(3) 的拉姆齐数是 6（见图）。 但直到 1955 年，R(4) 才被确定为 18。R(5) 仍然未知 — 它至少为 43，但不大于 48。尽管这些数字很小，但筛选所有可能的颜色是不可能的加州理工学院的 David Conlon 说。 考虑具有 43 个节点的完整图上的着色数。 “你有 903 条边； 每一种都可以用两种方式着色，”他解释道。 “所以你得到 2⁹⁰³，这简直是天文数字。”

随着集团规模的增加，确定拉姆齐数的任务只会变得更加困难。 Erdős 打趣说，与数学要求苛刻的外星人进行全面战争比尝试更容易 计算出 R(6)，介于 102 和 165 之间。不确定性的范围迅速扩大：根据 由 Stanisław Radziszowski 编制的估计, R(10) 小到 798 大到 23,556。 但是数学家的目标远远超出了 Ramsey 数 10。他们想要一个能够很好地估计 R(k)，甚至——或特别是——当 k 非常大。

“我不知道有哪个组合数学家没有至少一点点考虑过这个问题，”Wigderson 说。 “我认为这个问题真的很特别。”

法庭上的命令

弗兰克·拉姆齐 (Frank Ramsey) 是一个兼收并蓄、才华横溢的人物，他在 26 岁时就去世了。 就在他去世前几周， 伦敦数学学会学报 出版 论文 他在其中介绍了拉姆齐数。 那项工作甚至不是关于图形的，而是关于数理逻辑中的一个问题。 Ramsey 证明满足特定条件的陈述必须至少在某些时候为真。 其中一个条件是有一个大的场景“宇宙”来测试这个陈述。作为这个结果的垫脚石，Ramsey 证明了 Ramsey 数是有限的。

五年后，Erdős 和 Szekeres 证明了拉姆齐数 k 小于4^k. 12年后， 埃尔多斯表示 它大于 $latex sqrt{2}^k$。 为此，他计算了具有随机颜色边缘的图形包含单色集团的可能性。 这种“概率”技术在图论中产生了巨大的影响。 它还捕获了 R(k) 在两个呈指数增长的球门柱之间：$latex sqrt{2}^k$ 和 $latex 4^k$。

随着几十年的流逝，许多数学家试图缩小拉姆齐数可能值之间的差距。 有些人成功了：1975 年，Joel Spencer 下限翻倍. 以及一系列论文 康龙, 安德鲁托马森 和 阿什温·萨 推低了上限 到 4 年将增加约 $latex 2^{log(k)^2020}$。但与 Ramsey 数的边界大小相比，这些调整很小。 相比之下，Erdős 和 Szekeres 的公式 R(k) < 4^k 将是一个指数级的改进，随着 k 变大。

“这似乎只是一个可爱的小问题，”说 罗伯·莫里斯，巴西里约热内卢纯粹与应用数学研究所 IMPA 的一名数学家，与 Campos、Griffiths 和 Sahasrabudhe 共同撰写了这项新成果。 “欣赏起来有点微妙。 但人们真的很关心它。” 这可能是轻描淡写的说法。 “如果他们在 1936 年证明了这一点，人们会说，好吧，这有什么大不了的？” Béla Bollobás 说，他是 Morris 和 Sahasrabudhe 在孟菲斯大学的博士生导师。 “从那时起，事实证明这是一个非常大的问题，因为多年来，已经有数千篇论文讨论了拉姆齐问题的各种变体。” 作为 藤本植物Yepremyan，埃默里大学的数学家，说，“Ramsey 数在组合学与概率和几何学之间架起了一座桥梁。”

博弈论

 2018 年 XNUMX 月，Sahasrabudhe 在 IMPA 的 Morris 手下做博士后研究员。 两人希望与在附近的宗座天主教大学任教的格里菲斯一起开始一个新项目，当时 康伦的一篇论文 引起了他们的注意。 该论文概述了一种可能的策略，可以使 Ramsey 数呈指数级提高。 Griffiths、Morris 和 Sahasrabudhe 开始研究这个想法。

“一开始真的很令人兴奋，”Sahasrabudhe 回忆道。 他说，他们只花了大约一个月的时间就草拟了他们的论点。

他们的计划是建立在 Erdős 和 Szekeres 最初证明 $latex R(k) < 4^k$ 的想法之上。 为了证明 Ramsey 数最多为 $latex 4^k$，想象一下在具有 $latex 4^k$ 个节点的完整图上玩游戏。 游戏有两名玩家。 首先，你的对手将每条边涂成红色或蓝色，希望以一种避免产生单色集团的方式给边涂色 k 节点。

一旦你的对手完成着色，你的工作就是寻找一个单色集团。 如果你找到一个，你就赢了。

要赢得这场比赛，您可以遵循一个简单的策略。 它有助于思考（比喻）将您的节点分类到两个桶中。 一个桶中的节点将形成一个蓝色团，另一个桶中的节点将形成一个红色团。 一些节点将被删除，再也听不到了。 一开始，两个桶都是空的，每个节点都是进入其中一个的候选者。

从您喜欢的任何节点开始。 然后查看连接边。 如果一半或更多的边是红色的，则删除所有蓝色边和它们连接的节点。 然后将您最初的选择放入“红色”桶中。 该节点的所有红色边都仍然存在并且完好，从桶内紧贴着图的其余部分。 如果一半以上的边是蓝色的，则类似地删除红色的边和节点，并将其放入蓝色桶中。

重复直到没有节点为止。 （由于图是完整的，任何一点的每个剩余节点都连接到两个桶，直到它被放入其中一个。）

完成后，查看水桶内部。 因为一个节点只有在它的蓝色邻居被消除后才进入红色桶，所以红色桶中的所有节点都由红色边连接——它们形成一个红色团。 同样，蓝色桶形成一个蓝色集团。 如果您的原始图表至少有 $latex 4^k$ 个节点，则可以证明这些桶之一必须至少包含 k 节点，保证原始图中的单色集团。

这个论点聪明而优雅，但它让你建立了两个派系——一个蓝色的和一个红色的——尽管你真的只需要一个。 Conlon 解释说，总是变红会更有效率。 在这种策略下，您将在每一步选择一个节点，擦除其蓝色边缘，然后将其放入红色桶中。 红色的桶会很快装满，你会聚集一个红色的小圈子 k 节点时间减半。

但是您的策略必须适用于任何红蓝颜色，并且很难知道您是否总能找到具有大量红色边缘的节点。 因此，按照 Conlon 的建议，冒着遇到几乎没有红色边的节点的风险。 这将迫使您立即删除图表的很大一部分，让您在节点用完之前争先恐后地建立自己的集团。 为了实施 Conlon 的建议，Griffiths、Morris 和 Sahasrabudhe 需要证明这种风险是可以避免的。

开卷考试

在更新他们的游戏玩法时，Griffiths、Morris 和 Sahasrabudhe 遵循了稍微迂回的路线。 他们并没有直接通过将节点扔进红色和蓝色桶中来建立单色集团，而是首先专注于构建一种称为红皮书的结构。

在图论中，一本书由两部分组成：一个是单色集团，称为“书脊”，另一个是不同的节点集群，称为“页面”。 在一本红色的书中，连接书脊内节点的所有边缘都是红色的，连接书脊和页面的边缘也是红色的。 但是，页面内连接节点的边可以是任何颜色组合。 康伦在他 2018 年的论文中指出，如果你能在书页中找到一个红色集团，那么你可以将它与书脊结合起来以获得更大的红色集团。 这使您可以将对大型红色集团的搜索分解为两个更容易的搜索。 首先，寻找一本红色的书。 然后在书页中寻找一个小集团。

Griffiths、Morris 和 Sahasrabudhe 想要调整游戏获胜算法，以便它建立一本红皮书而不是一个红色集团。 虽然他们在项目开始几周后就确定了这个计划，但要让它发挥作用还需要数年时间。 他们仍然需要避免失去所有红边的威胁。

“我们被困了很长时间，”2021 年加入该项目的坎波斯说。

今年一月，四位数学家同意改用另一个版本的问题。 那个版本听起来更复杂，但事实证明更容易。

一直以来，该团队一直专注于拉姆齐数 R（k)，也称为“对角”拉姆齐数。 大小为 R(k） 必须包含 k 节点，全部由相同颜色的边连接，但该颜色是红色还是蓝色并不重要。 另一方面，“非对角线”拉姆齐数 R(k, l) 衡量一个图在包含一个红色集团之前必须有多大 k 节点，或一个蓝色的集团与 l 节点。 该小组没有继续破解对角线问题，而是决定尝试非对角线版本。 这被证明是有启发性的。

“很长一段时间，感觉就像你推开的每一扇门都被闩上了，或者至少很难通过，”格里菲思说。 “在那次改变之后，你感觉每一扇门都打开了。 不知何故，一切似乎都奏效了。” 在非对角线版本中，他们找到了一种按照特定协议一次删除一堆蓝色边缘的方法，这增加了红色边缘的密度，并导致改进了非对角线拉姆齐数的界限。 这种称为“密度增量”论证的方法以前曾用于求解 组合学中的其他重要问题, 但它没有被用于 Ramsey 数问题。

然后，四位数学家使用非对角线拉姆齐数的新界限为对角线结果扫清了道路。 到 1935 月初，他们终于以指数因子降低了拉姆齐数的极限，这是数学家近一个世纪以来一直追求的成就。 他们通过对 Erdős 和 Szekeres 在 XNUMX 年提出的相同论点进行现代化改造来做到这一点。

厄普西隆，厄普西隆

16月XNUMX日会谈后，与会者开始证实传闻。 Sahasrabudhe 演讲中的照片通过电话和私人信息流传开来——甚至是在 模糊但暗示性的帖子 在数学家 Gil Kalai 的博客上。 Campos、Griffiths、Sahasrabudhe 和 Morris 声称已经证明 $latex R(k) < 3.993^k$。 当晚，四位作者 在线发布他们的论文，让数学家们自己看到新的证明。

“我认为我们中的许多人根本没想到会在我们的一生中看到这样的改善，”他说 马蒂亚·布契奇，普林斯顿大学和高等研究院的数学家。 “我认为这是一个绝对惊人的结果。”

许多专家希望，随着指数级障碍的倒塌，更多的进展将很快随之而来。 这篇新论文的作者有意没有将他们的方法推向极限，以避免不必要的细节使他们的论点蒙上阴影。 “我对这种方法实际能走多远很感兴趣，因为我不知道，”坎波斯说。

“这是一个非常巧妙、绝对精彩的证明，也是一个真正的突破。 所以现在我希望闸门被打开，”Bollobás 说。 “我相信，三年后，辩论将围绕可能的改进展开。 我们可以将 3.993 提高到 3.9 吗？ 也许到3.4？ 那 3 个呢？

新证明有 56 页，每一个细节都需要数周时间才能得到组合学界的全面验证。 但同事们都很乐观。 “这群作者，他们是非常认真的人。 他们是非常非常擅长非常技术性的事情的人，”Wigderson 说。

谈到他的合作者，格里菲斯表示同意。 “与优秀的人一起工作是一种荣幸，不是吗？ 我认为这是我非常感激的，”他说。 “如果他们把它交给我，我可能还要再花五年时间才能把细节弄好。”