新的数学证明发现，无序在较大的图表中持续存在
在70多年的不妥协之后，数学界最顽固的数字之一终于动摇了。
在9月下旬发布的一份长达四页的证明中，大卫·康伦(David Conlon)和阿萨夫·费伯(Asaf Ferber)对“多色拉姆齐数字”(Coloror Ramsey Numbers)做出了迄今最精确的估计。多色拉姆齐数字衡量的是，在不可避免地表现出某种模式之前，
德国卡尔斯鲁厄理工学院(Karlsruhe Institute Of Technology)的玛丽亚·阿克森诺维奇(Maria Axenovich)说：“宇宙中没有绝对的随机性。”“总是有秩序的集群，拉姆齐的数字将其量化。”
图形是由线(边)连接的点(顶点)的集合。数学家特别感兴趣的是，在不同种类的子结构出现之前，它们可以包含多少顶点和边。
普林斯顿大学的玛丽亚·丘德诺夫斯基(Maria Chudnovsky)说：“如果你有一个足够大的图表，那么其中有很大一部分是排列得非常紧密的。”“很难解释为什么有些东西是美丽的，但人们普遍认为这是一种美丽的现象。”
Ramsey数涉及一种称为单色集团的特殊图案，它是一组顶点，它们在执行特定的着色过程后都通过相同颜色的边相互连接。
拉姆齐数字的变化取决于你要寻找的集团的大小和你用来着色的颜色的数量。数学家不能计算大多数拉姆齐数，因为除了最小的图之外，所有的图都太复杂了，无法直接分析。
通常，数学家能做的最好的事情就是为拉姆齐数设定一个可能的值范围。这就好像你想知道一个朋友的位置，但却只能确定他们在迈阿密以北，费城以南。
与Paul Erdő在20世纪30年代和40年代首次研究拉姆齐数以来的任何结果相比，新的证明更多地是对拉姆齐数的精确值进行了归零。加州理工学院的Conlon和加州大学欧文分校的Ferber发现了多色Ramsey数的一个新的“下限”，其精确度比之前的最佳估计值高出指数倍。他们的结果为数学家们提供了一个新的理解，让他们对图中的有序性和随机性之间的相互作用有了新的理解，这是数学中的基本兴趣。
由英国博学者弗兰克·拉姆齐(Frank Ramsey)在20世纪20年代引入的拉姆齐数(Ramsey Numbers)，最好通过例子来理解。从一个有五个顶点的图开始。把它们中的每一个都连接起来，形成数学家们所说的一个完整的图。现在，您是否可以将每条边着色为红色或蓝色，而不创建一组由相同颜色的边相互连接的三个顶点？答案是：你可以。
但是从一个包含六个顶点的完整图开始，现在如果不创建一个至少包含三个顶点的单色集团，就不可能用两种颜色给边上色。或者，换句话说，对于两种颜色和一个大小为3的集团，Ramsey数是6(因为它需要一个包含6个顶点的完整图)。
拉姆齐数字根据你要寻找的单色集团的颜色数量和大小而有所不同。但总的来说，它们很难精确计算，数学家只知道少数情况下的精确值。即使是规模为5(两种颜色)的小集团，他们最多也只能说拉姆齐数在43到48之间。
斯坦福大学(Stanford University)研究生尤瓦尔·威格德森(Yuval Wigderson)说：“这真的很尴尬。”“我们在这个问题上已经研究了近100年，但我们什么都不知道。”
拉姆齐数很难计算，因为随着顶点的增加，图的复杂性会急剧增加。对于一个有六个顶点和两种颜色的图，你可以手动浏览所有的可能性。但是对于一个有40个顶点的图来说，有2780种方法可以应用两种颜色。
在研究拉姆齐数的数学家中，有一个寓言，通常被归功于Erdő，它捕捉到了这些计算变得多么令人望而生畏的速度。有一天，敌对的外星人入侵。他们提出，如果我们能得出正确的拉姆齐数，我们就能保住地球。根据这个寓言，如果他们向规模为5的双色集团索要拉姆齐数，我们就应该动用人类文明的所有资源来寻找它。但如果他们要求6人的集团，我们应该做好战斗准备。
阿森诺维奇说：“如果他们问我们拉姆齐的数字是6，那就算了吧，我们会发动攻击。”
因为精确的拉姆齐数在很大程度上是不可能计算出来的，所以数学家们转而研究它们，证明它们大于某个“下界”，小于某个“上界”。这项新工作提高了下界的精度，但没有解决上限问题。
1935年，Erdős和George Szekeres建立了第一个这样的界限。他们用一个简短的证明证明了双色Ramsey数一定小于4t的上界，其中t是你感兴趣的单色集团的大小。他们还发现，三色拉姆齐数必须小于27t。十年后的1947年，Erdős计算出了这些数的第一个下界：对于两种颜色，顶点是($LaTeX\SQRT{2}$)t，对于三种颜色，是($LaTeX\SQRT{3}$)t。
($LaTeX\sqrt{2}$)t和4t之间有很大的区别，特别是当t变得非常大的时候。这一差距反映了数学家对拉姆齐数的不精确理解。但界限的形式--所需图形的大小以所需集团的大小表示--暗示了数学家们最想知道的东西。
新泽西州普林斯顿高等研究院博士后研究员丽莎·索尔曼(Lisa Sauermann)说：“我们真正想要了解的是，随着集团规模的扩大，这些(拉姆齐)数字的增长行为。”
出于这个原因，Erdő对拉姆齐数研究最持久的贡献不是界限本身，而是他用来计算界限的方法。以下是他为下限所做的事情。
假设你有一个完整的图，有10个顶点和45条边。假设您想知道是否可以在不创建特定大小的单色集团的情况下应用三种颜色，比如五个顶点(由10条边连接)。
您可以像erdős那样，从随机给边缘上色开始。对于每一条边，滚动等同于三面骰子的骰子，然后涂上任何出现的颜色。ERDő知道，任何特定的10条边的子集最终都是相同颜色的概率很容易计算。这只是一条边是红色的概率，是另一条边是红色的概率的倍数，以此类推，所有10条边都是红色的(也就是1/3 10)。接下来，他将该值乘以3，以说明有三种不同的颜色可以产生所需的单色集团。
然后，ERDő观察了图中五个顶点的不同集团的总数。一共有252个。最后，他计算了其中一个人产生单色集团的概率，并将其与其他251个人中任何一个产生该集团的概率相加。这是一种被称为“并集边界”的计算，它估计当您随机给边缘着色时产生单色集团的可能性。
只要并集边界保持在1以下，您就知道随机着色方法不能保证生成给定的单色集团。在我们的示例中，工会边界是0.0128。这意味着你远不能保证有5个顶点的单色集团，这意味着本例中的Ramsey数大于10个顶点。
数学家称这种方法为概率方法。对于一个原本难以解决的问题，这是一个巧妙的解决办法。Erdő不需要寻找不包含不同大小的单色集团的着色示例，而是简单地证明了这些无集团着色肯定存在(因为并界小于1)-这意味着拉姆齐数必须大于当前随机着色的图中的顶点数。
威格德森说：“我们能够证明某些东西的存在，而不需要实际展示它是什么。”
在接下来的70年里，数学家们只对Erdő的两色和三色下限进行了一次改进--1975年，乔尔·斯宾塞(Joel Spencer)逐渐收紧了这一下限。很多人都在研究这个问题，但没有人能找到比概率方法更好的方法来计算拉姆齐数。康伦说：“问题在于试图打破随机抽样带来的这个[界限]。”
新的证明改进了三种或三种以上颜色的Ramsey数的下界。
在Conlon和Ferber的工作之前，三种颜色的下限是($LaTeX\sqrt{3}$)吨(约1.73吨)。他们把下限提高到了1.834吨。对于四种颜色，他们把下限从2吨提高到了2.135吨。这两个都是巨大的飞跃。通过将基数增加到t的幂，Conlon和Ferber证明了存在指数级大的缺少所需单色团的三色图和四色图。换句话说，他们表明，在比之前已知的更大的曲线图中，无序现象可以持续存在。
Conlon和Ferber的目标是在不创建大型单色集团的情况下为完整的图形上色。为了做到这一点，他们想出了一种方法，在随机应用其余颜色之前，按照固定的规则有效地分配一种颜色(红色)。这种混合方法为他们提供了对图形结构的额外控制，这是Erdő所没有的。
对于计划的固定部分，他们将顶点放置在一种特殊的几何空间中，这样每个顶点都由一组坐标定义。然后，他们通过一个分两步的过程来决定将哪些边缘涂成红色。
首先，他们获取每个顶点的坐标，将它们平方，然后将它们相加--这一过程被称为平方和。由于这种特殊几何空间的性质，这种平方和运算产生了两个值之一：0或1。接下来，他们只关注平方和为0的顶点，计算出顶点对之间的“内积”--这是线性代数中的标准运算。如果一条边连接了一对内积是某个值的边，他们就把它涂成红色。这占了全部边缘的一半。
在完成了他们方法的这个确定性部分之后，Conlon和Ferber进入了随机部分。对于剩下的边缘，他们抛硬币-就像erdő所做的那样-来决定给给定的边缘涂蓝色还是绿色。
事实证明，这种方法是一种很好的方法，可以避免随着图形大小的增长而形成单色集团。这是经过设计的：这两个人设计了确定性的步骤，以生成散布在整个图表上的红边。从远处看，它们看起来几乎就像是随机散布的--事实上，康伦和费伯将这种红色边缘的排列称为“伪随机”。
这种红色边缘的伪随机分布实现了两个理想的结果。首先，通过展开红色边缘，它可以确保您不会出现任何大型红色集团(如果您想增加下限，这是您试图避免的)。其次，广泛分布的红边打破了图表，留下了更少的空白，最终可能会被另一种颜色的单色集团随机填充。
费伯说：“我们想确保我们确定使用的第一种颜色减少了潜在集团的数量。”
数学家们对新的证明反应迅速。在发布后的几天内，Wigderson发布了一篇后续论文，使用他们的方法证明了四种或更多颜色的Ramsey数的一个更好的下界。在拉姆齐数字停滞了几十年之后，大坝终于决堤了。
威格德森说：“自从40年代的Erdő以来，我们的知识状态就一直停滞不前，所以任何为这类问题提供新方法的东西都是令人兴奋的。”
