作者 | 贝爽、青暮
继四色猜想之后，超图着色猜想也被数学家攻克了。这距离超图着色猜想初次被提出已经过去近50年，距离四色猜想被证明，也已经过去了45年。
而证实这一猜想是来自英国伯明翰大学的五位数学家，他们分别是Daniela Kühn、Deryk Osthus、Tom Kelly、Abhishek Methuku以及Dong yeap Kang。其中前两位为资深数学家，后三位为博士后。
在1月份提交的一份预印论文中，他们采用线性超图的算法对三种极端超图案例进行了实验，在确保重叠边缘不出现相同颜色的情况下，证明了着色的数目永远不会大于超图中顶点的数目。
论文链接：https://arxiv.org/pdf/2101.04698.pdf
1
进阶版的四色猜想
四色定理又称为四色地图定理：如果在平面上划出一些邻接的有限区域，那么可以只用四种颜色来给这些区域染色，使得每两个邻接区域染的颜色都不一样。
这个问题最早是由南非数学家法兰西斯·古德里在1852年提出的，并与费马大定理、哥德巴赫猜想并列世界三大数学猜想。
图注：四色定理的一个案例。
人们发现，要证明宽松一点的“五色定理”（即“只用五种颜色就能为所有地图染色”）很容易，但四色问题却出人意料地异常困难。曾经有许多人发表四色问题的证明或反例，但都被证实是错误的。
1976年，数学家凯尼斯·阿佩尔和沃夫冈·哈肯借助电子计算机首次得到一个完全的证明，四色问题也终于成为四色定理。这是首个主要借助计算机证明的定理。四色定理的本质正是二维平面的固有属性，即平面内不可出现交叉而没有公共点的两条直线。
四色问题还可以转化为拓扑学版本，即更为抽象的图论版本。
图论是数学的一个分支，它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。
这里的转化指的是一种对偶的概念，即将一个地图转化为图论中的一个无向平面图。
图注：将平面四色问题转化为图论四色问题。
具体来说，是将地图中的每一个国家用其内部的一个点代表，作为一个顶点。如果两个国家相邻，就在两个顶点之间连一条线。这样得到的图必然是一个平面图（不会有两条边相交），而与每个国家选取的代表点无关。
图论版本的四色定理可以叙述为：必然可以用四种颜色给平面图的顶点染色，使得相连的顶点颜色不同。
而在图论领域，还存在一种超出日常直觉（或者说欧几里得直觉）的图形——超图，超图中的边可以连接多于两个顶点。超图也有着对应的“四色猜想”——超图着色猜想，可以称之为进阶版的四色猜想。
50年前，保罗·埃尔德斯（Paul Erdős）和另外两位数学家提出了一个图论（ Graph theory）问题。
Paul Erdős
他们认为，要给线性超图的边着色所需要的的颜色数量将不会超过图形的顶点数量。
值得一提的是，Erdős曾提出过数以千计的问题，但这个着色猜想是他最喜欢的三个猜想之一。为鼓励更多数学家来解决它，Erdős还将悬赏金增加到了500美元，但近50年来，没有一个人取得成功。
2
超图着色猜想的诞生
1972年秋天，两位颇具影响力的数学家保罗·埃尔德斯（Paul Erdős）和拉斯洛·洛瓦兹（László Lovász）来访，科罗拉多大学教授万斯·费伯（ Vance Faber ）举办了一场学术交流会。
值得一提的是，László Lovász在国际上享有盛誉，上个月他刚刚与美国普林斯顿高等研究院教授艾维·维格森（Avi Wigderson）共同获得了被誉为数学界“诺贝尔奖”的阿贝尔奖。此次表彰旨在奖励他们“对理论计算机科学和离散数学的基础性贡献，以及在将它们推动至现代数学的中心领域方面的领导作用。”
据悉，该奖项与菲尔兹奖、沃尔夫数学奖并称国际数学界“三大奖”。
在会上，Erdős、Faber和Lovász三位学者将谈话的重点聚焦在了超图（Hypergraphs）上，超图是当时图论学中一个很有趣的新概念。经一番辩论之后，他们提出了一个问题：在一定的约束条件下，为超图的边着色所需的最小颜色数。后来它被称为Erdős-Faber-Lovász猜想。
Faber现在是国防分析研究所计算科学中心（ Defense Analyses’ Center for Computing Sciences）的数学家，他说，“当时我们认为这是会上最简单的问题，第二天就可以解决，显然我们低估了它”。事实证明，这个问题比预期的困难要大得多。
后来，Erdős, Faber and Lovász 三人提出了一种新的图形结构——超图。普通图形由顶点和边线连接而成，每条边正好可以连接两个顶点，相比之下，超图没有这方面的限制：它们的边可以链接任意数量的顶点。
这种概念从直观上可能比较难想象，但宽泛的边概念使超图比以同类图更加通用。标准图只能表示成对事物之间的关系，比如社交网络中的两个朋友（每个人都由一个顶点表示）。但是要表达两个以上的人之间的关系，就像一个团队中的共享成员一样，每个边需要包含两个以上的人，这是超图所能呈现的。超图模型的基本设定就是一个边可以包含大于 2 个点，去拟合多元关系。
图注：超图的图示，其中每条边可以连接超过两个的顶点，上图中三个方框里的超图都只有三条边。
然而，这种多功能性是有代价的：超图比普通图更难证明其普适性。
IDC Herzliya和耶路撒冷希伯来大学的Gil Kalai说：“当你转向超图时，（图论的）许多奇迹要么消失，要么变得更加困难”。
例如在边着色问题上。在为超图上色过程中，若顶点处相交的两条边没有相同颜色，这种情况下所需的最小颜色数被称为图的色指数。Erdős-Faber-Lovász猜想是关于一类边重叠最小的超图的着色问题。在这些被称为线性超图的结构中，两条边最多只能在一个顶点重叠。比如在一个线性超图中，边a连接顶点1、2、3，边b连接2、3、4是不被允许的，但连接1、4、5是允许的。这个猜想预言：线性超图的色指数永远不会超过它的顶点数。
换句话说，如果一个线性超图有九个顶点，不管如何绘制，它的边都可以用不超过九种颜色着色。
此次论证的作者之一的Dong yeap Kang教授表示，为了证明这一猜想的普适性，他们挑战了着色问题最极端三种超图案例。
3
三种极端超图案例
通常情况下，随机绘制一个线性超图，它的颜色指数可能都会远远小于顶点数，但在三种特殊超图下会出现例外。
第一种超图被称为完全图（ Complete Graph），它的每条边只连接两个顶点。由于每一对顶点都由一条边连接，具有奇数个顶点的完全图具有Erdős-Faber-Lovász猜想所允许的最大色指数。
第二种超图在某种意义上，与完全图相反。当一个完全图中的边只连接少量顶点（两个）时，这类图中的所有边都连接大量顶点（随着顶点总数的增加，每个边所包含的数目也会增加），它被称为有限射影平面，和完全图一样，它也有最大的色指数。
第三种超图属于过渡情况——小边只连接两个顶点，大边连接多个顶点。在这种类型的图中，通常有一个特殊的顶点通过单独的边连接到其他每个顶点，然后有一个大的边将其他所有的顶点都连接起来。
如果调整三种特殊超图中的一个，结果通常也会具有最大的色指数。因此，这三个例子中的每一个都代表了一个更广泛的且具有挑战性的超图家族，这些超图多年来阻碍了数学家证明Erdős-Faber-Lovász猜想的努力。
当数学家第一次遇到这个猜想时，他们可能会尝试通过生成一个简单的算法过程来证明——指定要分配给每个边的颜色。需要强调的是，该算法需要适用于所有的超图，并且只使用与顶点数量相同的颜色。
另外，三个特殊的超图家族的形状差异很大，因此，任何证明可能给其中一个家族着色的技术，在另外两个族的超图中都是失败的。如Kang所说，“很难有一个共同的定理来包含所有的特殊情况。”
虽然Erdős、Faber和Lovász知道这三种极端超图，但他们不知道是否还有其他的超图具有最大的色指数。在这次最新论证中，来自伯明翰大学的5位数学家证明了包括这三种情况在内的所有超图，它们所需的颜色数量都少于其顶点数。Abhishek Methuku说：“如果把这三种超图家族排除在外，我们就可以证明没有其他的特殊例子了。”
4
按序着色，小边采用“吸收”法
需要说明的是，这个新证明是建立在罗格斯大学Jeff Kahn教授的研究基础之上的。Jeff Kahn在1992年证明了Erdős-Faber-Lovász猜想的近似版本。
去年11月，伯明翰大学两位资深数学家Kühn和Osthus，与Kang、Kelly和Methuku三位博士后组成团队着手改进Kahn的结果，以试图解决全部猜想。
Methuku表示，在刚开始工作时，他们就意识到也许能够准确地证明这个猜想。他说，“非常幸运的是，不知何故，我们所拥有的团队正好有解决这个问题的能力。”
该团队结合许多技术创建了一个覆盖所有类型的线性超图的算法。首先，他们根据边的大小（由边连接的顶点数决定）将给定超图的边分为不同的类别。
按大小排序之后，优先处理最难上色的边，也就是具有多个顶点的边（简称大边）。在大边着色处理上，他们采取了一种简化策略：将边重新配置为普通图的顶点（每个边只连接两个顶点），使用标准图论的既定结果上色，然后将这种着色转换回原始的超图。
在最大边着色之后，按大小依次排序，最后处理最小边。之所以采取这种策略是因为小边接触的顶点较少，更容易上色。不过，把它们留到最后也会在某种程度上增加着色的难度，如在处理小边时，许多可用的颜色已经在相邻的边上使用了。
为了解决这个问题，他们利用了组合学中提出的一种新技术——吸收（Absorption）。此前，该技术帮助他们解决了其他一系列问题。如Kalai说，“丹妮拉（Daniela）和德雷克（Deryk）在研究其他著名问题时用它得到了很多结果。现在他们又用这种方法证明了[Erdős-Faber-Lovász]定理。
具体来说，他们使用“吸收”将颜色逐渐添加到每一个边，同时确保所有边的着色始终保持正确的属性。这种方法特别适用于许多小边聚集在一个顶点上的情况，比如第三种超图中连接到所有其他顶点的特殊顶点，像这样的集群几乎使用了所有可用的颜色，并且需要仔细着色。
为了做到这一点，他们从这些集群中汇集并创造了一个小边存储库，然后，再对剩余的小边使用随机着色程序（通常采用滚动模具来决定给边使用哪种颜色）。此外，随着着色的进行，他们战略性地在从未使用的颜色中进行选择，并将其应用于存储库中的边，以“吸收”到颜色中。
“吸收”提高了随机着色过程的效率。随机对边进行着色是一种非常好的通用处理方法，但这种方法也带来了一种浪费，比如如果应用于所有边，它不可能产生最佳的颜色配置。相比之下，通过“吸收”来补充随机着色更具灵活性，这是一种更精确的方法。
他们对超图的最大边着色后，用吸收法和其他方法对较小的边着色，研究显示对任何线性超图的边着色所需的颜色数永远不会超过顶点数，这证明了Erdős-Faber-Lovász猜想是正确的。
由于概率的存在，它们的证明只适用于足够大的超图——那些具有超过特定数量顶点的超图，不过，这种超图在组合数学中很常见，因此，它只省略了有限个超图，数学家们认为它几乎可以称得上是一个完整的证明。
https://news.ycombinator.com/item?id=26706570
https://www.quantamagazine.org/mathematicians-settle-erdos-coloring-conjecture-20210405/#
500元卡时GPU资源「限时」免费领！
并行AI云 面向AI深度学习和高性能计算，提供A100、V100、T4等丰富的云算力资源；预置TensorFlow、PyTorch等环境，开箱即用；三线专家团队7x24小时在线提供多元化服务，助开发者提升科研效率，降低科研成本。
欢迎扫码免费体验~