上个月在网上发表的一篇论文驳斥了53年前的一个猜想，即给网络节点分配颜色的最佳方式。这篇论文仅用三页纸就展示更好的方法来给网络图上色。

网络图着色问题是近200年来数学家们研究的一个热点问题，它的灵感来自于如何将相邻区域的颜色映射成不同的颜色。目标是弄清楚如何给某些网络的节点上色，这样就不会有两个连接的节点“共享”相同的颜色。根据具体情况，网络着色可思想可以用来安排如何让客人在婚礼上就座，可以安排工厂任务，甚至解决数独难题。

图的着色问题往往易于表述，但往往很难解决。四种颜色是否足以为任何图形着色？

直到现在，这篇新论文所处理的问题似乎也不例外。它涉及张量积——由两种不同的图(称为G和H)以特定的方式组合而成的图。G和H的张量积是一个新的、更大的图中，其中每个节点代表原始图中的一对节点，一个来自G，一个来自H，并且张量积中的两个节点都连接在一起。

假设你是一位音乐老师，想为五年级的音乐会找到一对好的二重唱组合。您可以制作一个以学生为节点的图表，并在每一对相处得很好的学生之间建立链接。如果你有两种乐器之间的连接，如果你有以它们为特色的二重唱乐谱，那么你可以制作第二个图表，其中每个节点都是不同的乐器。这两个图的张量积对于一个学生和一个乐器的每一个可能的配对都有一个节点，只要两个学生在一起工作得很好，而且这两个乐器兼容，两个节点就会连接起来。

斯蒂芬在他的博士论文中推测，张量积所需的最小颜色数与其两个构成图之一所需的颜色数相同 。这是图论中的一个主要猜想。”

几十年来，数学家们积累了大量的证据，其中一些证据表明这个猜想是正确的，另一些则是错误的。对于哪种可能性最终会占上风，数学家们有不同的猜测。但至少每个人似乎都同意，这个问题很难解决。

多伦多瑞尔森大学的安东尼博纳托表示：“我个人认为，这个猜想应该是正确的，因为很多聪明人都看过这个猜想，如果存在的话，他们应该已经找到了一个反例。”

但现在，俄罗斯数学家雅罗斯拉夫提出了一种构造这种反例的简单方法：张量积需要的颜色比两种构成图中的任何一种都少。这个证明“很简单，但很巧妙”。

张量图与不同的图之间如何映射的问题密切相关，在数学领域，斯蒂芬的猜想可能是最大的开放问题，这是一个重要的突破。

五颜六色的聚会

为了对你能从一张张量图上色中收集到的信息有所了解，想象一下你计划邀请朋友到你的乡村庄园度过一系列的周末。作为一个好的主人，你想要聚集那些喜欢彼此陪伴的人。

你知道，你的一些朋友有同样工作，他们可以立即联系。同样，你知道每个朋友都有自己的爱好，这也是客人们发现共同兴趣的另一种方式。你想，会拉大提琴的舞蹈老师可能喜欢和会打网球的瑜伽教练谈笑风生，但可能很难和集邮的政治科学家交谈。你希望参加任何聚会的每一对客人都能找到一些共同感兴趣的领域，无论是通过工作还是爱好，你想知道在邀请名单上的每一个人之前，你需要举办多少次聚会。

• 雅罗斯拉夫发现了一个与斯蒂芬提出的已有53年历史的图论猜想相反的例子。

您可以使用节点为作业的图来表示不同作业之间的关系，并使用链接连接任何两个不利于共享业务对话的作业。同样，您可以制作一个节点是不同爱好的图表，并在两个爱好不兼容时将它们连接起来。

这两张图的张量积将为每个工作—爱好配对有一个节点，如果两个工作和两个爱好都不相容，两个节点就会连接起来——这正是你在周末请客时想要避免的情况。现在，您可以为张量的节点着色以使连接的节点具有不同的颜色，那么将为您提供一种方法来形成不同周末的访客列表：您可以在“绿色”周末邀请与绿色节点对应的人员，“红色”周末邀请与红色节点对应的人等，保证不相容的客人将在不同的周末访问。您使用的颜色数量可以告诉您日历中要“关闭”的周末数量。

从这个例子中需要注意的一件事是，任何工作图的有效着色都可以延续到张量积——你可以使用的相同颜色简单地将每个工作爱好的颜色组合到他们的工作中。这样的色彩可以很好的安排聚会，每一对客人都是完全基于他们共同的职业兴趣。

从表面上看，斯蒂芬的推测似乎不太可能。毕竟，如果你把你的张量着色建立在工作图的着色基础上，你就忽略了你所知道的关于你朋友的兼容爱好的所有事情，并且有可能把本来可以相处得很好的客人分开。相反，如果你把你所有关于工作和爱好的信息结合起来，也许你可以少用一些颜色，享受一些应得的免费周末。

然而，在50多年的时间里，数学家们找不到一个张量积比它的两个组成图中的颜色更少。在更广泛的“分数”颜色设置中也是如此，在这种情况下，每个节点都可以分配一组颜色——可能是2/3黄色和1/3绿色。(就周末家庭聚会而言，这可能相当于有三个不同的朋友打网球，邀请其中两个在“黄色”周末，第三个在“绿色”周末。)

这些发现暗示了这个猜想可能是正确的，但是其他的发现却提出了相反的观点。例如，数学家们已经证明，斯蒂芬的猜想对于需要无限多种颜色的图或者对于每个链接都有一个首选向的矢量图来说是不成立的。但是，即使数学家们在一些更广泛的背景下证明了斯蒂芬的猜想，并在另一些更广泛的背景下证明了它的错误，他们似乎也无法在斯蒂芬最初考虑的设置中解决它：有限的、无向的、带有非分色的图。

普林斯顿大学的Noga Alon说:“人们普遍认为这很可能是真的，但无论如何，这是非常困难的。”

着色页面

雅罗斯拉夫现在用一个清晰、简单的例子，从这些不确定性中找到答案，证明斯蒂芬猜想是错误的。在一篇论文中，他展示了如何构造一种张量积，这种张量积所需的颜色比它的任何一个组成图都要少。

雅罗斯拉夫首先考虑当把一个图G和它的一个“指数”图结合起来形成一个张量积时会发生什么。一个指数图对于G的每一种可能的颜色都有一个节点，每个节点都有固定数量的颜色(这里，我们允许每一种可能的颜色，而不只是连接节点的颜色不同)。如果图G有7个节点，而调色板有5种颜色，那么指数图就有5^7个节点——因此得名“指数图”。

• 斯蒂芬·海德涅米关于两张图的张量积所需要的最小颜色数的猜想，半个多世纪以来一直没有得到解答。

将我们的注意力返回到颜色上，其中连接的节点应该是不同的颜色，我们不能保证调色板中的五种颜色足以为图G着色;同样，它们可能也不足以给57节点的指数图上色。但数学家们早就知道，有一个图形，这五种颜色足以着色:由G和它的指数图构成的张量积。

事实上，所有的指数图都有这样的性质：把指数图和它所建立的图结合起来的张量积可以用与最初用来制作指数图的调色板完全相同的颜色来着色。雅罗斯拉夫通过展示如何构建一个图G来反驳史蒂芬的猜想，使得G和它的指数图都需要比调色板中更多的颜色。

史蒂芬宣称自己“非常高兴”自己的猜想在这么多年后得到了解决。希托夫在一封电子邮件中写道，他的证明“具有某种优雅、简单和明确的品质”。

数学家们说，这个新的反例很聪明，很有创意，不需要任何复杂、前沿的数学工具。“对于图理论家来说，你可以用两句话来解释这个结构，”卡莱说。

为什么这样的论点被忽视了50多年对数学家来说是一个谜。“有时候，一小块宝石会被树叶覆盖，”黑尔说。“他只是比任何人都更深刻地理解了这一点。”

雅罗斯拉夫的图是巨大的：虽然他没有精确计算出它们有多大，但他估计G图可能至少有4^100个节点，而指数图至少有4^10000个节点——这个数字远远大于可观测宇宙中粒子的估计数量。

再说一次，“巨量”是在旁观者的眼中。对于雅罗斯拉夫来说，他的反例“不是特别大”.他说。“在数学领域也有反例(与之相比)，这确实是一件小事。”

虽然你不可能邀请4^100名客人到你的乡间别墅做客，但雅罗斯拉夫的研究并没有排除存在更小的反例。既然数学家们已经知道史蒂芬的猜想是错误的，那么下一个自然的问题就是它有多错误：一个张量积可能比它的组成图少多少种颜色，以及这样的反例能有多少节点和链接。

同时，这篇新论文给数学家上了重要的一课。有时候，一个猜想很难被证明的原因很简单，那就是它是错误的。