50年前，一场茶话会上提出的超图边着色猜想终获证明：颜色数永远少于顶点数

选自Quantum Magazine

作者：CHARLIE WOOD

机器之心编译

编辑：小舟，杜伟

历时近半个世纪，数学领域的一个著名猜想——Erdős-Faber-Lovász 超图边着色猜想，终于得到了证明！

1972 年秋季，当时为科罗大多大学新晋教授的 Vance Faber 与两位颇具影响力的数学家 Paul Erdős 和 László Lovász 举办了一场茶话会。席间，他们谈到了当时图论领域很有潜力的新理论超图（hypergraph）。一番讨论之后，他们提出了一个问题，即后来的 Erdős-Faber-Lovász 猜想——某些限制下为超图的边着色所需要的最少颜色数。

左：已故匈牙利数学家 Paul Erdős；右：匈牙利数学、2021 阿贝尔奖获得者之一 László Lovász。

我们知道，普通图由顶点构建而成，这些点由边连接。每条边连接两个顶点，而超图的边可以连接任意数量的顶点。着色问题旨在为图或超图的所有边着色，使得顶点处相交的两条边具有不同的颜色。这一过程中所需要的最少颜色数被称为色度指数（chromatic index）。Erdős 猜想认为线性超图的色度指数永远不会超过其顶点数。

对于这个猜想，三位数学家都认为非常简单，并扬言「第二天就能解出来」。但遗憾的是，他们失败了，该问题比预想中的难多了。为此，Paul Erdős 将其列为自己最喜欢的三个猜想之一，并为证明出猜想的人提供奖励。自此，Erdős 猜想就成为了图论领域的著名问题，吸引很多人尝试解答，但没有人成功。

2021 年 1 月，在提出近 50 年后，英国伯明翰大学数学系的几位研究者终于证明了 Erdős 猜想。他们对某些超图的边加阴影所需的颜色数进行了限制，这样重叠边不会出现相同的颜色。他们证明：为超图边着色所需的颜色数永远不会多于顶点数。

论文地址：https://arxiv.org/pdf/2101.04698.pdf

就采取的方法而言，研究者结合了以往方法，特意留出超图的一些边并随机为其他边上色。这种方法在 Erdős 他们提出猜想时无法实现。对此，匈牙利数学、2021 阿贝尔奖获得者之一 László Lovász 表示：「我非常高兴这个猜想终于得到了证明，这真是一件美丽的作品。」

3 种极端超图

如果你绘制了一张线性超图，会发现它的色度指数可能远远小于顶点数，但也有三种极端超图可以推动了极限。

第一种情况，每个边仅有两个顶点，通常被称为完全图，每对顶点通过一条边连接。顶点数为奇数时的完全图具有 Erdős 猜想所允许的最大色度指数。

完全图（Complete graph）。

第二种极端超图正好与完全图相反。完全图中的边仅连接两个顶点，而第二种超图中的所有边都连接大量的顶点，并且顶点总数越多，每条边包含的顶点数也随之增加。这种超图被称为有限摄影平面，并且和完全图一样，它也具有最大色度指数。

有限摄影平面（finite projective plane）。

在第三种极端超图中，通常有一个特殊的顶点通过孤立的边与其他顶点相连，然后一条大边将其他顶点都连起来。

如果你对以上三种极端超图稍作修改，则结果也通常具有最大的色度指数。这三种极端超图都各自代表了一种更具挑战性的超图族。多年来，这些极端超图一直是数学家们证明 Erdős 猜想的障碍。

在证明该猜想时，数学家首先想到的是，创建一种简单的算法或者步骤以指定分配给每条边的颜色。但这种算法需要适用所有超图，并且使用到的颜色数量与顶点数相同。任何一种算法解决了其中一种超图，但对另外两种超图都不奏效。

论文一作 Kang 表示：「很难发现一种涵盖所有极端情况的普遍定理。」

在猜想提出时，Erdős、Faber 和 Lovász 了解这三种极端超图，但不清楚是否存在其他具有最大色度指数的超图。Kang 等在论文中证明了，与这三种极端超图明显不同的其他任何超图需要的颜色数量也要少于顶点数。

边分类

Kang 等人的新证明建立在罗格斯大学数学教授 Jeff Kahn 先前研究的基础上，后者于 1992 年证明了类似于 Erdős 猜想的另一个超图着色猜想。2020 年 11 月，Kang 等人就开始改进 Kahn 的研究结果，虽然当时没有完全证明该猜想。

研究者先基于边数量（一条边连接的顶点数）将给定超图的边分为几种不同的种类。

在完成边的分类后，他们首先转向最难着色的边（具有多个顶点的边）。他们为大边着色时采取了一种简略化的策略，将这些边重构为普通图的顶点（其中每条边仅连接两个顶点）。接着利用标准图论的既定结果为这些边着色，然后将颜色传输回原始超图，迭代这一过程。

Jeff Kahn 表示，这种做法将过去几十年来的各种方法都用上了。

在为最大边着色后，研究者将最小边的着色留在了最后。这是因为小边连接的顶点更少，因而更容易着色。但是，最后为小边着色也可能增加着色的难度，这时很多可用的颜色已经用在了其他相邻的边上。

为了解决这一问题，他们利用到了组合数学中的一种新方法——吸收法（absorption ），并最终利用这种方法证明了 Erdős-Faber-Lovász 猜想。

吸收法

研究者使用吸收法：在着色过程中，逐渐添加边，同时确保着色过程满足原猜想的要求。在有许多小边收敛到一个单点上的情况（例如在第三个极端超图中，有一个特殊的顶点与其他所有顶点连接），这类超图几乎使用到了所有可用的颜色。

吸收法提高了随机着色过程的效率，随机对边进行着色对于通用程序来说是很好的基础方法，但这种方法也很浪费。如果将其应用于所有的边，就不可能产生最佳的颜色配置。但是最新的证明显示：可以用吸收法完善这种方法，以削弱随机着色法的灵活性。这是一种更精确的方法。

最后，研究者使用一种算法为超图的最大边着色，然后使用吸收法等对较小的边着色。研究者由此证明为任何线性超图的边着色所需的颜色数永远不会超过顶点数。这就证明了 Erdős-Faber-Lovász 猜想是正确的。

原文链接：https://www.quantamagazine.org/mathematicians-settle-erdos-coloring-conjecture-20210405/

CVPR 2021 线下论文分享会

为更好的服务 AI 社区，促进国内计算机视觉学术交流，机器之心计划于 6 月 12 日组织大型「CVPR 2021 线下论文分享会」。

本次活动将设置  Keynote、 论文分享和 Poster 环节 ，邀请顶级专家、论文作者与现场参会观众共同交流。欢迎论文作者、AI 社区从业者们积极报名参与。

点击阅读原文 ，了解详情并参与报名。

© THE END 

转载请联系本公众号获得授权

投稿或寻求报道：content@jiqizhixin.com