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

发布时间：2023-05-11 09:07:41 所属栏目：外闻来源：

导读：拉姆齐数（Ramsey number）是整个数学领域中最难计算的数。拉姆齐数源于拉姆齐理论（Ramsey Theory），它是数学中的一个分支，主要研究在一定条件下结构中存在的规律性或者秩序。其基本观点是，在足够大的结构中，一

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

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

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

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

上面已经提到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年后，Erdős证明它大约是，

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

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

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

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

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

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

（编辑：汽车网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!