作者：Kelsey Houston Edwards 2021-4-5 译者：zzllrr小乐 2021-4-6
1972年秋天，万斯·费伯（Vance Faber）成为科罗拉多大学的新教授。当两位有影响力的数学家保罗·厄多斯（Paul Erdős）和洛维斯（László Lovász）来访时，费伯决定举办一个茶话会。厄多斯尤其享有古怪和精力充沛的研究者的国际声誉，费伯的同事也渴望与他见面。
费伯说："当我们在那里的时候，就像在很多这样的茶会上一样，厄多斯会坐在一个角落里，被他的粉丝们包围着。"他会同时进行讨论，通常用几种语言讨论不同的事情。
厄多斯，费伯和洛维斯聚焦谈论超图，这是当时图论中很有前途的新想法。经过一番辩论，他们得出了一个问题，后来被称为厄多斯-费伯-洛维斯猜想。它涉及在某些限制范围内为超图边着色所需的最小颜色数量。
“（这是）我们能想出的最简单的事情，”费伯说，他现在是国防分析研究所计算科学中心的数学家。“我们在聚会上花了点力气，当时说，'哦，好吧，我们明天会搞定'。（然而）这从未发生过。”
事实证明，这个问题比预想的要困难得多。厄多斯经常宣称这是他最喜欢的三个猜想之一，并提供了一个奖励，增加到500美元，因为数学家意识到了其困难性。这个问题在图论界是众所周知的，并吸引了许多人尝试来解决它，但没有一个是成功的。
但是现在，近50年后，一个由五位数学家组成的团队终于证明了这个茶话会沉思的正确。在1月份发布的预印本中，他们得到了遮蔽某些超图边缘所需的颜色数量的极限，以便没有重叠的边缘具有相同的颜色。他们证明颜色的数量永远不会大于超图中的顶点数。
这种方法小心地撇开图的一些边缘，随机给其他边缘着色，这是研究人员近年来为解决一些长期存在的开放问题而运用的一些想法的组合。当厄多斯、费伯和洛维斯想到这个问题时，他们无法得到这种方法。但原来三人数学家中的现在还健在的两位，可以盯着这个问题的解，好好享受他们的好奇心激发的数学创新的乐趣。
"这是一个漂亮的成果，"埃特维斯·洛伦德大学的洛维斯说。"我真的很高兴看到这一进展。
恰好足够的颜色
当厄多斯、费伯和洛维斯喝茶谈论数学时，他们脑海里有了一种新的图状结构。普通图形由点（称为顶点）构建，由线条连接，称为边（缘）。每条边正好连接两个顶点。但厄多斯、费伯和洛维斯考虑的超图限制较少：它们的边可以连接任意数量的顶点。
这种更广阔的边的概念使得超图比他们的中心辐射型更通用。标准图只能表达成对事物之间的关系，比如社交网络中的两个朋友（每个人以顶点表示）。但是，要表达两个以上的人之间的关系——就像一个群体中的共享成员一样——每个边都需要包含两个以上的人，这是超图允许的。
然而，这种多功能性是有代价的：与普通图相比，很难证明超图的通用特性。
IDC赫兹利亚和耶路撒冷希伯来大学的吉尔·卡莱（Gil Kalai）说：“当你转到超图时，许多（图论的）奇迹要么消失，要么变得更加困难。”
例如，超图的边着色问题更困难。在这些场景中，目标是对图（或超图）的所有边进行着色，这样在顶点相遇的两个边没有相同的颜色。这样做所需的最小颜色数称为图的染色指标。
厄多斯-费伯-洛维斯的猜想是关于特定类型的超图的着色问题，其边缘重叠最小。在这些结构（称为线性超图）中，不允许两条边在多个（超过1个）顶点重叠。该猜想预测，线性超图的染色指标永远不会超过其顶点的数量。换句话说，如果一个线性超图有九个顶点，则不管怎样绘制它们，都可以用不超过九种颜色来给边染色。
厄多斯-费伯-洛维斯猜想的极端普遍性使得证明具有挑战性。当你转到具有越来越多的顶点的超图时，排列其循环边缘的方法也会成倍增加。在所有这些可能性情况下，似乎有可能有一些边，需要比它的顶点数更多的颜色。
"有太多不同类型的超图，它们有完全不同的味道，"Abhishek Methuku说，新证明的作者之一，以及Dong-yeap Kang, Tom Kelly, Daniela Kühn和Deryk Osthus，都在伯明翰大学。“这个结论是对的，令人惊讶。”
证明这种令人惊讶的预测，意味着面对几种对颜色特别具有挑战性的超图，并确定没有其他更难的例子。
三个极端超图
如果你在一页上涂鸦，画出一个线性超图，它的染色指标可能会远远小于它的顶点数。但有三种类型的极端超图，达到极限。
第一种类型，每条边只连接两个顶点。它通常被称为完全图（complete graph），因为每对顶点都由边连接。具有奇顶点数的完全图，具有厄多斯-费伯-洛维斯猜想允许的最大染色指标。
第二个极端的例子，从某种意义上说，与完全图相反。如果完全图中的边仅连接少量的顶点（两个），则此类图中的所有边缘都连接大量顶点（随着总顶点数量的增加，每个边所包含的数字也是如此）。它被称为有限的投影平面，并且，像完全图一样，它具有最大的染色指标。
第三个极端例子落在光谱中间，有小边（只连接两个顶点）和大边（连接许多顶点）。在此类图中，通常有一个特殊的顶点，通过单边连接到其他每个顶点，然后有一个单一的大边，将所有其他顶点都连贯起来。
如果稍微修改三个极端超图中的一个，结果通常也会具有最大染色指标。因此，这三个例子中的每一个都代表了一个具有挑战性的更大的超图家族，多年来，这阻碍了数学家证明厄多斯-费伯-洛维斯猜想的努力。
当数学家第一次遇到猜想时，他们可能会尝试通过生成一个简单的算法或一个简单的程序来证明这一点，该算法或程序指定一种颜色来分配给每个边缘。这种算法需要适用于所有超图，并且只使用跟顶点数一样多的颜色。
但是极端超图的三个家族的形状却大相径庭。因此，任何可能给其中一个家族着色的技术的证明，通常都因其他两个家族的超图而失败。
"很难有一个共同的定理来纳入所有的极端情况，"康说。
虽然厄多斯，费伯和洛维斯知道这三个极端的超图，他们不知道是否还有其他超图，也有最大的染色指标。新的证明更进一步。它表明，任何与这三个例子明显不同的超图都需要比其顶点数更少的颜色。换句话说，它确定，类似这三者的超图很难得到。
"如果你排除掉这三个家族，我们就可表明，没有更多不好的例子，"Osthus说。"如果你不太接近这三者，那么你可以使用明显较少的颜色。
排列边缘
新的证明建立在罗格斯大学的杰夫·卡恩（Jeff Kahn）的进展基础上，他在1992年证明了厄多斯-费伯-洛维斯猜想的近似版本。去年11月，Köhn和Osthus（都是资深数学家）和他们的三个博士后团队——康、凯利和梅图库——着手改进卡恩的结果，即使他们没有解决全部的猜想。
但他们的想法比他们预期的更强大。当开始工作时，他们开始意识到，也许能够确切地证明这个猜想。
"这都是魔法，"Osthus说。“很幸运，我们的团队某种程度上完全适应了它。”
他们首先根据边缘大小（边缘连接的顶点数量）将给定超图的边缘排序为几个不同的类别。
虚拟黑板上的数学笔记图片。Abhishek Methuku提供
作者结合了许多技术，创建了一个算法，涵盖所有类型的线性超图。上图是他们在这个过程中做的笔记。
排序后，他们首先转向最难着色的边缘：具有许多顶点的边缘。他们给大边涂上颜色的策略依赖于简化。他们将这些边缘重新配置为普通图形的顶点（每个边缘仅连接两个顶点）。他们使用标准图论的既定结果为它们着色，然后将着色返还给原始超图。
卡恩说：“他们正在糅合他们和其他人几十年来一直在开发的各种东西。”
在给最大边缘着色后，他们向下工作，将图形的最小边保存到最后。由于小边接触的顶点较少，因此它们更容易着色。但是，将它们保存到最后也从某种意义上说使着色更加困难：当他们到达小边缘时，许多可用的颜色已经用于其他相邻的边缘。
为了解决这个问题，作者利用了一种称为吸收（absorption）的组合学新技术，他们和其他人最近一直在使用这种技术来解决一系列问题。
"Daniela和Deryk有很多研究其他著名问题的结果，在使用它。现在，他们的小组设法用这种方法证明了[厄多斯-费伯-洛维斯]定理，"Kalai说。
吸收颜色
作者使用“吸收”，一种逐渐给着色添加边缘，同时确保沿途着色始终保持正确性质的方法。它特别适用于着色的地方，是许多小边共点于单个顶点，例如第三个极端超图中，特殊的顶点连接到所有其他顶点。像这样的集群几乎使用到所有可用的颜色，并需要仔细着色。
为此，作者从这些棘手的集群中创建了一个小型边缘库。然后，他们应用了随机着色程序，给剩下的许多小边着色（基本上是，滚动骰子，以决定哪种颜色适用于给定的边）。随着着色的进行，作者战略性地从未使用的颜色中进行选择，并以精心选择的方式进行应用，"吸收"到着色中。
“吸收”可提高随机着色过程的效率。随机着色边是一个非常通用的程序的一个很好的基础，但它也产生浪费 - 如果应用于所有边缘，它不太可能产生颜色的最佳配置。但最近的证明通过“吸收”来抑制随机着色的灵活性，这是一种更精确的方法。
最后，作者用一种技术给图形的最大边缘涂上颜色，然后用“吸收”和其他方法给较小的边缘涂上颜色，从而证明任何线性超图边缘所需的颜色数量永远不会超过顶点的数量。这证明厄多斯-费伯-洛维斯的猜想是正确的。
由于概率元素，他们的证据只适用于足够大的超图，即那些具有超过特定数量的顶点数的超图。这种方法在组合学中很常见，数学家认为它几乎完全证明了这一点，因为它只省略了数量有限的超图。
Lovász说："论文中仍然认为节点的数量必须非常大，但这可能只是一些额外的工作。"基本上，这个猜想现在已经被证明了。
厄多斯-费伯-洛维斯的猜想开始于一个问题，似乎可以在一个聚会的范围内提出和回答。在随后的几年里，数学家们意识到这个猜想并不像听起来那么简单，这也许是三位数学家所希望的。唯一比解决茶会上的数学问题更好的事情之一是想出一个最终激励了几十年的数学创新， 并最终解决它的方式。
卡恩说："证明它所做的努力，让我们发现了具有更多普遍应用的技术。"这是厄多斯在数学中的收获方式。
联系客服
