四色猜想是数学中最著名的猜想之一，即任何地图是否只能用四种颜色着色。这个猜想已经被证明是正确的，但是它的导数问题仍然让数学家们着迷。最近，一位俄罗斯数学家发表了一篇三页纸的论文，推翻了这个领域存在了53年的一个重要猜想。

今年5月在网上发表的一篇论文推翻了53年前提出的一个猜想，提出了图着色问题的一个新的最优解。这篇论文只有三页长，但它证明了对于一些特定的网络，有许多数学家没有想到的更好的解决着色问题的方法。

绘图着色的问题起源于人们在给地图着色时的思维，——至少要用多少种颜色才能保证地图中相邻边界的国家或地区的颜色不一样？为了解决这个问题，数学家们研究了近200年。

这个问题可以进一步简化：给网络的每个节点染色，使任何两个相连的节点具有不同的颜色。至少需要多少种颜色？解决这个问题可以帮助我们更高效地处理日常生活中的很多场景，比如婚礼上如何给客人安排座位，或者不同时间给工厂安排任务，甚至解决数独问题。

图的着色问题往往很简单，但很难证明。即使打开这个领域的问题，即任何地图是否可以只用四种颜色着色，相邻两个区域的颜色是否不同，这个问题已经解决了一个世纪。如果你想知道，答案是肯定的。)

这篇新发表的论文并没有推翻“四色法则”，而是提出了更好的解决方案。这个问题之所以50多年没有解决，是因为它涉及到一个复杂的张量积问题，即由两个不同的图形(在图论中称为G和H)以特定方式组成的新图形。G和H的张量积是一个更大的新图，其中每个节点代表原始图中G和H的一对节点。此外，如果张量积中的两个节点在g和h中相连，那么它们也是相连的。

想象一下，如果你是一名音乐老师，你想为五年级孩子的音乐会找到一个好的二重唱组合。可以这样画两幅图：一幅图中，不同的点代表不同的学生，点与点之间的联系意味着两个学生相处融洽，可以配对；在另一幅图中，不同的点用于表示不同的乐器，点之间的连接表示包括这两种乐器的二重奏的乐谱。然后，这两张图的张量积所包含的点代表一个学生和他能演奏的乐器。如果张量积中的两点相连，就意味着两个学生可以很好的相处，乐器的种类也可以是搭档，可以组成二重奏。

1966年，现为克莱姆森大学教授的斯蒂芬赫代涅米(Stephen Hedetniemi)在博士论文中提出，填充张量积所需的最小颜色数与填充组成张量积的两个图形所需的颜色数相同。"这是图论中一个非常重要的假设."耶路撒冷希伯来大学的吉尔卡莱说，“许多研究人员都思考过这个问题。”

几十年来，数学家们已经积累了一系列关于这个猜想的研究证据，其中一些表明它是正确的，而另一些则认为它是错误的。虽然数学家们对这个猜想是否正确有不同的看法，但似乎每个人都同意证明或证伪它是非常困难的。

“我个人认为这个猜想应该是真的，因为很多聪明人都研究过，如果真的有，应该已经能找到反例了。”多伦多瑞尔森大学的安东尼博纳托说。

但是现在，俄罗斯数学家雅罗斯拉夫什托夫提出了一个简单的方法来建立反例：填充张量积比填充两个分量的图需要更少的颜色。加拿大本那比西蒙弗雷泽大学的Pavol Hell认为这种方法“简单但非常聪明”。

地狱指出，张量积与不同图形应该如何相互映射的问题密切相关。在数学领域，Hedetniemi猜想可能是最大的开放性问题之一。“这篇论文的发表是一个重要的突破”。

为了更好地理解着色张量积的思维模式能解决什么实际问题，请想象这样一种情况：你计划在几个周末邀请不同的朋友参加你的乡村庄园聚会，作为一个细心的主持人，你希望把那些有共同话题的人聚集在一起。

你知道你的一些朋友有工作，所以他们可以立即建立联系，但其他人没有。同样，你知道每个朋友都有一个爱好，所以客人可能会找个人通过聚会分享他们的兴趣和爱好。你希望在每一次聚会上，每两位客人都能找到一些共同语言，无论是工作上还是爱好上。你想知道需要组织多少聚会来邀请名单上的所有人。

你可以用一张图片来表示不同工作之间的关系。不同的点代表工作和点之间的联系。

接代表两个工作之间没有共同话题。(这听起来好像标反了，但是这样的连接方式在图着色问题中是有意义的，因为我们最终需要用颜色来区分有问题的配对方式。)同样地，你可以用另一张图来表示不同兴趣爱好之间的关系，点之间的连接代表两个兴趣爱好之间不存在共同话题。

这两个图的张量积将为每个工作-爱好配对提供一个节点，如果两个工作和两个爱好都不存在共同的话题，则两个节点相连——这正是你希望在聚会时避免发生的情况。

现在，你可以为张量积的节点着色，使得相互连接的节点具有不同的颜色，从而得到一份在不同周末组织聚会的访客列表。你可以在“绿色”周末邀请绿色节点对应的朋友，“红色”周末邀请红色节点对应的朋友，以此类推，从而确保没有共同话题的客人将在不同的周末参加聚会。所使用的颜色数量可以告诉你在日历中需要被预留的周末的数量。

从这个例子中可以注意到的是，在与工作相关的图形中，任何有效着色都会延伸到张量积——在着色时，可以简单地将每个工作-爱好组合的节点直接用工作对应的颜色着色。如果根据这种着色方法组织聚会，那么每对客人将完全基于他们共同的职业兴趣进行交谈，无论他们的爱好如何。同样地，任何在兴趣图中的着色方式也可以延伸到整个张量积的图中。Hedetniemi 猜想，在两张图的着色方法中，使用颜色较少的是为张量积着色的最佳方法。

从表面上看，Hedetniemi 的猜想似乎不太可信。毕竟，如果你基于工作图的着色进行张量积的着色，就得忽略朋友们之间存在的共同爱好，那些本来非常合适在一起聚会的客人可能就会被分开。反之，如果你把所有关于工作和爱好的信息结合起来，你或许就能用更少的颜色来预留周末安排聚会，为自己留出多一些清净的周末时光。

然而，五十多年来，数学家们仍然找不到任何一种张量积图形，可以用比组成它的两个图都要少的颜色来填充。他们发现，只要两个组成图中的一个着色时需要四种或更少的颜色，Hedetniemi 的猜想就是正确的。在更广泛的“分数”着色中也是如此，即每个节点可以分配一个颜色组合，例如 2/3 黄色和 1/3 绿色。(就上文提到的周末家庭聚会的例子而言，这相当于你有三个会打网球的记者朋友，你在标记为“黄色”的周末邀请其中两位，在标记为“绿色”的周末再邀请第三位。)

这些证据表明 Hedetniemi 的猜想可能是正确的，但也有证据指向了相反的方向。例如，数学家已经证明，对于需要无限多种颜色的图形或者是有向图(即其中的每个连接都有一个偏好的方向)，Hedetniemi 的猜想将不再适用。但是，即使数学家在一些更广泛的场景下证明了 Hedetniemi 的猜想，在另一些场景下又推翻了猜想，他们也似乎无法在 Hedetniemi 最初考虑的情形下解决它，即具有非分数着色的有限无向图。

终结争议

现在，Shitov 通过一个清晰、简单的证明终结了这些争议，证明 Hedetniemi 的猜想是错误的。在那篇研究论文中，他仅用了略多于一页密集的数学论证，便展示了如何构造一个张量积反例，使得填充它所需要的颜色比填充其任何一张组成图所需要的颜色都要少。

Shitov 首先考虑将图 G 与它的指数图(exponential graph)之一组合形成张量积的情况。用固定数量的颜色对 G 着色，每一种可能的情况在指数图中对应一个节点(这里允许每种可能的着色，而不仅仅是相互连接的节点着色不同的情况)。例如，如果图形 G 具有 7 个节点，而着色板中有 5 种颜色，那么指数图将有有 57 个节点，“指数图”的名字也由此而来。

接下来，看看相连节点颜色不同的着色方式。我们无法保证调色板中的 5 种颜色足以使图 G 着色;同样，它们可能也不足以给有 57 个节点的指数图着色。但是数学家早就知道有一张图，用这 5 种颜色就可以完成着色——G 和它的指数图生成的张量积。

事实上，所有指数图都具有以下属性：要给一张图及其指数图的张量积着色，使用的颜色数量可以等于生成指数图所需的颜色数量。Shitov 展示了如何构建一个图 G，使得 G 及其指数图都需要比张量积图中更多的颜色进行着色，从而反驳了 Hedetniemi 的猜想。

Stephen Hedetniemi 的猜想近半个世纪后终于被推翻。

Hedetniemi 的猜想历时几十年终于被推翻，他本人表示对此感到“非常高兴”。Shitov 的证据“具备一定的优雅和简洁，而且绝对优质，”他在一封电子邮件中写道。还有数学家认为，Shitov 举出的反例是聪明且有创造力的，它不需要任何复杂的、尖端的数学工具。“对图论的研究者而言，你可以用两句话解释它的构造，”Kalai 说。

至于为什么这样的论点一直被忽视了超过 50 年，这对于数学家们来说还是一个谜。“有时，一块小宝石常会被树叶覆盖，”Hell 说，“Shitov 只是设法比任何人都更深刻地理解它。”

Shitov 论文中举例的图非常庞大：虽然他没有精确计算它们的大小，但他估计图 G 可能至少有 4100 个节点，而指数图至少有 410000 个节点——这个数字远远大于可观测的宇宙中所有粒子的估计数量。

然而，“庞大”只存在于旁观者的眼中。对于 Shitov 来说，这次提出的反例“并不是非常巨大”。他说：“在数学研究中存在一些更大的反例，相比之下这个只是非常微小的一个。”虽然你不太可能邀请到 410000 位客人到你的乡村别墅进行聚会，但 Shitov 的工作并没有排除存在更小反例的可能。

如今，既然数学家知道 Hedetniemi 的猜想是错误的，那么自然地，下一个问题就是它到底错到什么程度——张量积需要的颜色可能比其组成图要少多少?这些反例的节点和连接数量最少是多少?

Alon 指出，这篇论文给数学家们提供了一个重要的教训：“有时候，一个猜想很难被证明，可能仅仅是因为它是错误的。”