这篇最新发表的论文也没有推翻“四色规则”,却提出了一种更好的解法。这一问题之所以 50 多年来一直都未能被解决,是因为它涉及到了复杂的张量积(tensor product)问题,即由两个不同的图形(图论中将其称为 G 和 H)以特定的方式组成的新图形。G 和 H 的张量积是一个更大的新图形,其中每一个节点都代表了来原始图形中的一对节点,分别来自 G 和于 H;并且,如果张量积中的两个节点在 G 中对应的节点和在 H 中对应的节点都是相连的,那么它们也是相连的。
1966 年,现为克莱姆森大学(Clemson University)教授的 Stephen Hedetniemi 在他的博士论文中提出,填充张量积时需要的最少颜色数量与填充组成它的两张图时需要的颜色数量较少的那张相同。“这是图论当中一个非常重要的假设。”耶路撒冷希伯来大学(Hebrew University of Jerusalem)的 Gil Kalai 说,“许多研究者们都思考过这个问题。”
Shitov 首先考虑将图 G 与它的指数图(exponential graph)之一组合形成张量积的情况。用固定数量的颜色对 G 着色,每一种可能的情况在指数图中对应一个节点(这里允许每种可能的着色,而不仅仅是相互连接的节点着色不同的情况)。例如,如果图形 G 具有 7 个节点,而着色板中有 5 种颜色,那么指数图将有有 57 个节点,“指数图”的名字也由此而来。
接下来,看看相连节点颜色不同的着色方式。我们无法保证调色板中的 5 种颜色足以使图 G 着色;同样,它们可能也不足以给有 57 个节点的指数图着色。但是数学家早就知道有一张图,用这 5 种颜色就可以完成着色——G 和它的指数图生成的张量积。
事实上,所有指数图都具有以下属性:要给一张图及其指数图的张量积着色,使用的颜色数量可以等于生成指数图所需的颜色数量。Shitov 展示了如何构建一个图 G,使得 G 及其指数图都需要比张量积图中更多的颜色进行着色,从而反驳了 Hedetniemi 的猜想。
Stephen Hedetniemi 的猜想近半个世纪后终于被推翻。图片来源:Courtesy of Stephen Hedetniemi