数论领域的一个巨大突破，四位数学家发现了“拉姆齐数”的新上限

luyuanhong

数论领域的一个巨大突破，四位数学家发现了“拉姆齐数”的新上限

作者：我才是老胡 中国科学院数学与系统科学研究院 2023-06-08 16:21 发表于北京



拉姆齐数（Ramsey number）是整个数学领域中最难计算的数。拉姆齐数源于拉姆齐理论（Ramsey Theory），它是数学中的一个分支，主要研究在一定条件下结构中存在的规律性或者秩序。其基本观点是，在足够大的结构中，一定会出现某种特定的子结构。这种理论最早是由英国数学家 Frank P. Ramsey 于 20 世纪初提出的，因此得名。



比如说，考虑一个有 n 个顶点的完全图（complete graph），也就是说每个顶点都和其他所有顶点相连。如果我们将图中每一条边染成红色或者蓝色，那么当 n 等于多少时才能确保图中存在一个红色的三角形或者蓝色的三角形呢？答案是 6 。证明过程见：《数学的魅力在于，在得到证明之前，一切都是可能的——拉姆齐理论》

1930 年，弗兰克·拉姆齐证明，如果一个图足够大，就不可能避免创建数学家称之为单色团（monochromatic clique）的东西——一个顶点的公共边要么全是红色，要么全是蓝色。

确切地说，一个图必须多大，才能迫使一个单色团出现？答案取决于团的大小。拉姆齐证明，存在一个数，现在称为拉姆齐数，表示对于给定大小的单色团必然存在的顶点的最小数量，无论边的颜色如何。

在上面的例子中 R(3,3)=6 。它表示，在一个有 6 个顶点的完全图中（共有 15 条边），所有的边要么是蓝色，要么是红色；那么这个完全图的边中一定会存在一个由 3 个蓝色边组成的完全子图，或者存在一个由 3 条红色边组成的完全子图。这里的 R 就是拉姆齐数。





拉姆齐理论的核心思想是，我们无法创造一个完全混乱的系统。

事实上，计算拉姆齐数是非常困难的，没有人能够计算出所有拉姆齐数。他们所能做的最好就是找到它可能的极限（或界限）。在上个世纪，数学家 Paul Erdos 和他的合作者首次确定了拉姆齐数的上界。然而，自那时以来，这个上界几乎没有改变。

然后，今年 3 月，研究人员宣布他们已经将拉姆齐数的上界提高了一个指数级别。这是一个相当轰动的成果。

但拉姆齐数的大小很难确定。1935年，在拉姆齐证明它存在的五年后，埃尔德什和 George Szekeres 为给定大小的团提供了一个新的、更紧密的拉姆齐数上界。但从那时起，数学家几乎无法改进埃尔德什和 Szekeres 的计算。

前几个拉姆齐数相对容易计算。显然，R(2)=2 ，由于一个包含两个顶点的完全图只是就是一条边，而这条边必须是红色或蓝色。



更一般地说，R(k) ，或者 k 的拉姆齐数，是顶点的最小数量，超过该数量，图就无法避免包含一个大小为 k 的团。

上面已经提到 R(3)=6 。直到 1955 年，R(4) 才被确定为 18 。R(5) 仍然未知——它至少为 43 ，最大不超过 48 。一个具有 43 个顶点的完全图，具有 903 条边，每条边都可以用两种方式着色，那么着色的可能情况有 2 的 903 次方之多。可见确定计算 R(5) 已经几乎不可能。

随着团的大小增加，确定拉姆齐数的任务变得更加困难，R(6) 在 102 和 165 之间。不确定性范围迅速扩大，据估计，R(10) 可以小到 798 ，大到 23,556 。但数学家的目标远远超出了 10 的拉姆齐数。他们想要一个公式，能够给出 R(k) 的一个好的估计值，尤其是当 k 非常大时。

拉姆齐数的界限



1928 年，拉姆齐证明了拉姆齐数是有限的。五年后，埃尔德什证明了 k 的拉姆齐数小于 4^k 。12 年后，Erdos 证明它大约是



为此，他计算了一个随机着色的图包含单色团的概率。这种“概率”在图论中产生了巨大的影响。

随着几十年的过去，许多数学家试图缩小拉姆齐数可能值之间的差距。1975 年，乔尔·斯宾塞（Joel Spencer）将下限提高了一倍。



到 2020 年，一系列论文将上限降低到了

但与拉姆齐数界限的大小相比，这些调整都很小。相比之下，对埃尔德什公式 R(k)＜4^k 中的 4 进行任何减少都将是一个指数级的改进，随着 k 变大，这个改进会迅速增长。



一个小游戏

2018 年 8 月，Conlon 的一篇论文引起了 Sahasrabudhe 等三位数学家的注意。



这篇论文概述了一种可能的策略，可以对拉姆齐数进行指数级的改进。

这种策略是基于埃尔德什最初证明 R(k)＜4^k 的思想。为了证明拉姆齐数最多是 4^k ，想象在一个有 4^k 个顶点的完全图上玩一场游戏。游戏有两个玩家。首先，你的对手会将每条边染成红色或蓝色，并且试图避免形成一个包含 k 个顶点的单色团。一旦你的对手完成了染色，你的任务就是寻找一个单色团。如果你找到了一个，你就赢了。

要赢得这个游戏，你可以遵循一个简单的策略，将顶点装进两个桶。一个桶中的顶点将形成一个蓝色团，另一个桶中的顶点将形成一个红色团。一些节点将被删除，永远消失。一开始，两个桶都是空的，每个节点都有可能进入其中一个桶。



从任何一个你喜欢的顶点开始。然后看连接的边。如果一半或更多的边是红色的，那么删除所有蓝色的边和它们连接的顶点。然后将你最初选择的顶点放入“红色”桶中。如果超过一半的边是蓝色的，你可以类似地删除红色的边和顶点，然后将其放入蓝色的桶中。

重复这个过程，直到没有剩余顶点。当你完成时，检查桶里的内容。因为一个顶点只有在其蓝色邻居被消除后才进入红色桶，所以红色桶中的所有顶点都通过红色边连接在一起 —— 它们形成了一个红色团。同样，蓝色桶中的顶点形成了一个蓝色团。如果最初的图有至少 4^k 个顶点，可以证明其中一个桶必须包含至少 k 个顶点，从而在原始图中保证一个单色团。

这个论证是巧妙而优雅的，但它让你构建两个团 —— 一个蓝色的，一个红色的 —— 尽管你实际上只需要一个。像 Conlon 解释的那样，始终选择红色会更有效。根据这个策略，你在每个步骤中选择一个顶点，擦除它的蓝色边，然后将它扔进红色桶。红色桶会迅速填满。

但是你的策略必须适用于任何红蓝着色，而且很难知道你是否总能找到一个有很多红色边的顶点。因此，遵循 Conlon 的策略存在一个风险，可能遇到一个几乎没有红色边的顶点。在这种情况下，你将不得不一次性删除大量蓝色边（以及与之相连的顶点）。这样做会让你在剩余顶点数量减少之前，急于构建一个单色的团。换句话说，在这种情况下，你需要在顶点数量耗尽之前迅速找到一个单色团。Sahasrabudhe 需要证明这个风险是可以避免的。

突破

在改进游戏策略时，Sahasrabudhe 采取了一种稍微麻烦的方法。他们没有直接通过将顶点点放入红色和蓝色桶中来构建单色团，而是首先集中精力构建一个名为红色书（red book）的结构。

在图论中，一本书由两部分组成：有一个单色团，称为“书脊（spine）”，还有一个称为“页（pages）”的独特顶点簇。



在红色书中，书脊内部顶点之间的边都是红色的，连接书脊和页的边也是红色的。然而，连接页内部顶点的边可以是任意颜色的组合。Conlon 在他 2018 年的论文中指出，如果你能在一本书的页中找到一个红色团，那么你可以将它与书脊相结合，得到一个更大的红色团。这样，你就可以将寻找一个大红色团的任务分解为两个更简单的搜索。首先，寻找一本红色书。然后，在书的页中寻找一个团。

Sahasrabudhe 等人希望建立一种能够构建红色书而非红色团的游戏获胜算法。但要让它成功还需要几年的时间。他们仍然需要化解失去所有红边的风险。

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

一直以来，该团队一直关注拉姆齐数 R(k) ，也称为“对角（diagonal）”拉姆齐数。一个大小为 R(k) 的图必须包含 k 个顶点，所有顶点由相同颜色的边连接，但这个颜色是红色还是蓝色都无所谓。另一方面，“非对角（off-diagonal）”拉姆齐数 R(k,l) 衡量一个图在多大程度上必须包含一个具有 k 个顶点的红色团或一个具有 l 个节点的蓝色团。与其继续尝试对角问题，小组决定尝试非对角版本。

在非对角版本中，他们找到了一种按照特定协议一次删除一堆蓝边的方法，这增加了红边的密度，并导致非对角拉姆齐数的改进界限。这种方法称为“密度增量（density increment）”论证，曾用于解决组合学中的其他重要问题，但在拉姆齐数问题上尚未使用过。

四位数学家随后利用非对角拉姆齐数的新界限为对角结果铺平道路。到 2 月初，他们终于将拉姆齐数的上界降低了一个指数级别，这是数学家们近一个世纪来一直在寻求的成就。

四位数学家声称已经证明


普林斯顿大学和高等研究院的数学家 Matija Bucic 说：“我认为我们中的许多人都没有想到在有生之年能看到这样的改进。”“我认为这是一个绝对了不起的结果。”这个新证明共有 56 页，组合学界需要花几个星期的时间来完全核实每一个细节。

来源：老胡说科学

常量

这个领域，更恰当的说是组合数学或者图论。