David Conlon和Asaf Ferber提出了多色Ramsey数值的下限。这些数字表示在不可避免的样式开始出现之前，您可以增加多少图形。
经过70多年的抵抗，一些数学上最顽固的数字终于开始屈服了。
在9月发布的四页证明 中，David Conlon和Asaph Ferber对“多色Ramsey数”给出了最准确的估计。这些数字描述了在某些模式不可避免地开始出现之前它们可以增长到的图形的大小。
“我们的宇宙中没有绝对的巧合，”德国卡尔斯鲁厄理工学院的玛丽亚·阿克塞诺维奇说。 “某处总是有很多簇，而拉姆齐数将其量化。”
图形是由线（边）连接的点（顶点）的集合。数学家对在图形中出现各种子结构之前可以向图形中添加多少个顶点和边的问题特别感兴趣。普林斯顿大学的玛丽亚·楚德诺夫斯基（Maria Chudnovsky）
说：“如果您的图形足够大，则其中很大一部分将是有序的。” “美丽很难用语言来解释，但是这种现象被认为是美丽的。” Ramsey数字指的是特定序列，即单色单击。这是一组顶点，在某些绘制过程之后，这些顶点将通过相同颜色的边缘相互连接。加州大学尔湾分校的Asaf Ferber
拉姆西数取决于所需的团的大小和为图形着色的颜色数。大多数Ramsey数不能由数学家计算，因为除了最简单的图以外，几乎所有图都很难直接分析。
数学家通常能够做到的最好的事情就是为Ramsey数指定一个可能的值范围。好像您想知道您的朋友现在在哪里，但是您设法建立的唯一条件就是他在莫斯科以南和索契以北的某个地方。
自帕尔多斯（Pal Erdos）首次开始研究这些数字以来，新的证明使之有可能比任何结果更准确地确定拉姆齐（Ramsey）数的值范围。在1930年代和40年代。加州理工学院的Conlon和加州大学欧文分校的Ferber发现了多色Ramsey数的新下界。事实证明，该精确度比以前的估计最好。他们的结果为数学家们提供了一种新的方式，使他们可以理解图中顺序和随机性相互作用的极其重要的方案。
“这是一个了不起的结果，”阿克塞诺维奇说。“我非常喜欢他。”
彩色链接
由英国普遍主义者 弗兰克·拉姆齐（Frank Ramsay）于1920年代发明的拉姆齐数的本质最容易通过一个例子来理解。让我们从具有五个顶点的图形开始。我们将每个顶点与所有其他顶点相连-正如数学家所说，我们得到一个完整的图。是否可以将所有边缘涂成蓝色或红色，以使图形不包含通过相同颜色的边缘成对连接的三个顶点？在这种情况下，可以。
但是，如果我们从一个包含六个顶点的完整图形开始，则无法在不生成三个或更多顶点的单色团的情况下用两种颜色绘制其边缘。换句话说，对于两种颜色和集团大小为3，Ramsey数将为6（图形必须至少具有6个顶点）。
拉姆齐数根据颜色数和所需单色团的大小而变化。但总的来说它们很难计算-确切的值仅在少数情况下才为数学家所知。即使单击5和2色，数学家也可以说Ramsey数更好-它在43到48之间。
“一个令人尴尬的情况，”斯坦福大学的研究生Yuval Wigderson说。 “我们从事这项任务已经有将近100年的历史了，但还没有学到任何东西。”
连接五个顶点以形成一个完整的图形。这样的图可以用两种颜色上色，这样就不会出现由相同颜色的边连接的三个顶点。
但是通过查看六个顶点的图，已经不可能避免出现三个这样的顶点。
Ramsey数很难计算，因为图的复杂度会随着顶点数的增加而迅速增长。对于六个顶点和两种颜色的图形，可以手动枚举所有选项。对于40个顶点的图形，有2780种方法可以将边缘着色为两种颜色。
“我们必须检查太多，”阿克塞诺维奇说。
研究拉姆齐数的数学家的故事通常被认为是Erds。她描述了这些计算变得太复杂的速度。想象一下，外星人入侵了地球。如果我们能够为拉姆齐数给出正确的值，他们愿意为我们的星球提供帮助。如果他们要求我们用大小为5的两种颜色和集团命名此案的拉姆齐编号，我们将需要投入人类的全部资源来解决此问题。如果他们要求我们为尺寸为6的集团计算拉姆齐数，那么对我们而言，立即进行战斗就更容易了。
Aksenovich说：“如果他们要求我们提供[点击大小] 6的Ramsey号码，那么最好立即发起攻击。”
学习随机性
由于基本上不可能计算拉姆西数的确切含义，因此数学家宁愿逐渐限制它们的值。他们证明该数字大于某个下限，并且小于一个上限。新工作提高了下限的精度，但没有提及上限。
1935年，Pal Erdos和Gyorgy Szekeres建立了第一个这样的边界。他们简短地证明了两种颜色的拉姆齐数必须小于4 t，其中t是您感兴趣的单色集团的大小。他们还发现这三种颜色的拉姆齐数应小于27 t。 10年后的1947年，鄂尔多斯（Erdos）计算了这些数字的第一个下限：对于两种颜色，它们是（√2）t顶点，并且对于三个（√3）t。
（√2）t和4 t之间有很大的差异，特别是在非常大的t值时。这种差距反映了数学家对拉姆齐数的模糊理解。但是，边界的形状-所需图形的大小如何表示所需图形的大小-暗示了数学家最感兴趣的内容。普林斯顿大学高级研究所的博士后莉莎·索尔曼（Lisa Sowerman）
表示：``我想了解的是这些Ramsey数是如何随集团的规模增长的。
因此，埃尔德对拉姆齐数的最长寿命贡献不是边界本身，而是边界的计算方法。这就是他计算下限的方式。
假设您有一个包含10个顶点和45个边的完整图形。想象一下，您需要找出是否有可能在不创建一定大小的单色团的情况下用三种颜色对边缘进行着色-假设为5（5个顶点由10条边缘连接）。
您可以像Erdös一样，通过随机绘制边缘开始。对于每个边缘，让我们滚动一个类似三边骰子的物体，并用随机出现的颜色对其进行绘画。鄂尔多斯知道，很容易计算10个边缘的任何子集最终变为相同颜色的概率。您只需要将一条边的一条概率为红色的概率乘以另一条边为红色的概率，以此类推，对所有十条边（依此类推，即1/3 10）。然后，他将该数字乘以三，以说明以下事实：三种不同颜色中的任何一种都可以生成所需的单色团。
然后，鄂尔多斯查看了图中五个顶点的不同点击总数。它们可以有252个，最后，他以其中一个将产生单色团的概率为基础，并将其添加到其余251个顶点中的任何一个都将产生此团的概率中。这就是所谓的。 “工会边界”的计算，当边缘随机着色时，给出了获得单色团的可能性。
只要连接边界保持小于1，您就会知道随机着色方法不能保证会出现给定的单色团。在我们的示例中，边框为0.0128。这与5个顶点的单色团的保证外观相差很远，这意味着在此示例中，Ramsey数大于10个顶点。
数学家将此方法称为概率方法。对于棘手的问题，这是一种巧妙的解决方法。 Erds没有寻找不包含不同大小的单色团的着色示例，而是简单地证明了这种不可单击的着色应该存在（因为联合边界小于1）。也就是说，Ramsey数必须大于我们随机着色的图形中的顶点数。
帕尔·埃多斯（Pal Erdos）发明了用于计算拉姆齐数的“概率”方法。
1）我们从10个顶点的完整图形开始。用三种颜色为边缘着色时，是否总能找到5个由10条相同颜色的边缘连接的顶点？
2）特定边缘为红色（而不是蓝色或黄色）
的概率为1/3 3）10个边缘为红色的概率为（1/3）10
4）总共，三种颜色可以生成单色团。
5）来自5个顶点的不同点击总数为252。
（1/3）10 * 3 * 252 = 0.0128-随机着色边缘时获得单色点击的概率。
威格森说：“我们可以证明某物的存在而无需直接展示。”
在接下来的70年中，数学家仅一次提高了Erds的下限两种和三种颜色-1975年，Joel Spencer对其进行了逐步改进。许多人都致力于解决这个问题，但是没有人能找到比概率方法更好的计算Ramsey数的方法。康隆说：“问题是由于随机抽样，试图解决这个限制。”
这正是Conlon和Ferber今年秋天设法做到的。
启用订单
新的证明改进了三种或更多种颜色的Ramsey数的下限。
在进行此工作之前，三种颜色的下限为（√3）t（约1.73 t）。 Conlon和Ferber将其提高到1,834吨。对于四种颜色，他们将下限从2 t提高到2.135 t。这两个结果都是巨大的进步。通过增加幂t的底数，Conlon和Ferber证明了没有单色团的指数大的三色和四色图的存在。换句话说，他们表明混乱发生在比以前认为的更大的图中。
Conlon和Ferber的目标是在不产生大型单色团的情况下为整个图形着色。他们提出了一种方法，可以根据固定的规则有效地分配一种颜色（例如红色），然后随机应用所有其他颜色。这种混合方法使他们可以控制Erds没有的图结构。
加州理工学院的David Conlon
固定规则表示顶点在特定几何空间中的分布，其中每个顶点由一组坐标定义。然后，他们在决定将哪些边缘涂成红色时遵循了两个步骤。
首先，他们获取每个顶点的坐标，将它们平方，然后加上它们以获得平方和。由于该几何空间的特殊性，平方和给出了两个值之一，即0或1。然后，它们只留下了总和为0的那些顶点，并计算了成对的顶点的点积（线性代数的标准运算）。然后，如果将连接点积等于某个值的一对顶点连接起来，他们将边缘绘制为红色。
在完成算法的确定性部分后，Conlon和Ferber转向了随机算法。对于其他所有边缘，他们都掷硬币（就像Erds那样），以确定它是绿色还是蓝色。
实践证明，这种方法是避免图形增长时出现单色点击的好方法。那是有意设计的：一对夫妇专门设计了确定性阶段，以使红色边缘在整个图形中均匀分布。乍一看，它们看起来像是随机分布的。实际上，Conlon和Ferber将此边缘着色称为“伪随机”。
红色边缘的伪随机分布实现了两个目标。首先，通过在整个图上散布红色边缘，我们确保图中没有出现大的红色点击（这是我们想通过增加下边框来避免的方法）。其次，散布在整个图表中的红色边缘将其分开，留下了较少的空白空间，这些空白可能会意外地被不同颜色的单色点击所填充。
“我们想确保我们使用的第一种颜色确定性地减少了潜在的点击次数，” Ferber说。
数学家对新证明很快做出了反应。发布后的几天，Wigderson出版工作下面这个，在这里使用，以提高他们的方法越低，Ramsey数与四色以上的情况的约束。经过几十年的停滞不前，拉姆西号坝终于被打破了。
“自鄂尔多斯时代以来，自40年代以来，我们对这一主题的知识就没有改变。因此，任何为我们提供一种解决此类问题的新方法的方法都引起了极大的兴趣，” Wigderson说。