博文

[转载] 张量积所需要的颜色数量比两种构成图中的任何一种都少

已有 2350 次阅读 2019-7-1 10:14 |系统分类:论文交流|文章来源:转载

3 页纸能做什么？推翻一个数学猜想！

(https://zh.wikipedia.org/zh-hans/图论)

Yaroslav Shitov是一名俄罗斯的数学家，5月，他在arXiv发表了一篇论文，在这篇只有3页长（主体部分仅有2页）的论文中，他推翻了数学家Stephen Hedetniemi在1966年提出的一个猜想。这是一个在图论中非常重要的猜想，几十年来，不断有数学家想要尝试解开这个难题，却一直无人能够判断它究竟是对是错，直到现在……

在介绍Hedetniemi的猜想之前，我们先要介绍的是另一个数学家们已经研究了200多年的热点问题，那就是如何在地图上给相邻的国家涂上不同的颜色。这一类问题启发了很多类似的数学研究，他们或许看起来容易，但解起来却非常难。这一领域中的四色地图问题便是这样一个猜想：用4种颜色足以给任何一张地图上色吗？数学家花了一个多世纪的时间，终于得到了肯定的答案。

数学家从地图着色问题中受到启发，继而开始探索网络（或者说“图”）中的节点着色问题。他们的目标是要弄清楚如何给图中的节点着上颜色，使得两个相连的节点颜色不一样。

这个问题与两个张量的张量积有关。张量积是两个不同的图（G和H）以某种特定的方式组合而成的更新、更大的图。在新的图中，每个节点代表着一对来自原始图的节点——一个来自G、一个来自H，而且如果两个在张量积中的节点是相连的，那么它们在H、G上的相应节点就也是相连的。

我们可以举个例子来解释它的意思。假设你是一名音乐老师，需要找两名学生来表演一场二重奏，你需要他们满足两个条件，一是能良好相处，二是演奏的乐器能够配合一场二重奏演出，那么你就可以制作两张图表：第一张图以学生为节点，将每一对合得来的学生连接起来；第二张图以乐器为节点，将所有可以组成二重奏的乐器两两相连。对于每一个学生和一种乐器的组合，在张量积中都会有一个节点，例如A对长号、B对小提琴。如此一来，当出现两个学生相处良好，且他们的乐器也可以配合演奏时，这两个节点就会连接起来。

53年前，Hedetniemi在他的博士论文中提出猜想：一个张量积所需的最少颜色数量，与组成它的两张图中需要颜色数量较小的那张相同。这么多年来，数学家们积累了很多与它有关的研究，有人相信它是正确的，有人觉得它不对。但如果它是错的，又没人能提供一个可以有效驳斥这个猜想的反例。

直到Shitov想出了一种简单而精妙的方法，成功地构造出了一个反例：张量积所需要的颜色数量比两种构成图中的任何一种都少。

一张张量图的着色，能告诉我们什么呢？我们可以举个例子：假设你要在一连好几周的周末都安排一些人前往某个地方度假，你需要以他们的职业和爱好为依据，让每个前往度假的人无论是通过职业还是爱好，都能找到与他有共同兴趣的人，然后将这些人安排到同一个周末。

张量图的着色能有效地帮助你处理这个问题，并能计算出需要多少个这样的周末才能安排完所有前去度假的人。

首先你要制作一张以职业为节点的图表，然后将那些不利于对话交流的工作连接起来；接着，再制作一张以爱好为节点的图，也将两个冲突或者说不兼容的爱好连接起来。

这两张图的张量积将为每个工作-爱好的配对生成一个节点，它连接的是两个在工作和爱好上都不相容的节点，也就是你需要在安排时避免的情况。接着，你可以对张量积的节点着色，给相连的节点着上不同的颜色。然后，再将颜色相同的节点所对应的人安排到一起，并且根据使用了的颜色数量，决定需要多少个周末。

这时候你可能会注意到，在职业节点图中的任何有效着色，都可以延续到张量积中。因此，你可以简单地将职业节点图中的着色运用到到张量积中的每个工作-爱好组合的着色中。这样一来，聚会中的每一对客人都是完全基于他们在职业上的兴趣，而非爱好上的兴趣而聚集在一起的。反之亦然。

Hedetniemi的猜想说明的是，这两张图中使用颜色更少的一种，是给张量图上色的最好方法。表面上看来，Hedetniemi的猜想似乎不太可行，因为如果张量图的着色是建立在职业图的着色基础上，那么所有关于爱好兼容性的信息就被全部忽略了，并且有可能会把原本可以相处愉快的人给分隔开了。但是，如果把所有关于职业和爱好的信息都结合起来，或许有可能少用一些颜色，用更少的周末就安排完了所有的人。

50多年来，数学家们一直没能找到一个所需颜色数量比组成图所需的颜色数量更少的张量积。1985年，数学家Mohamed El-Zahar和Norbert Sauer证明了当两个组成图中的其中一个所需颜色为4种或更少时，这个猜想是正确的。2011年，数学家朱绪鼎发表论文的证明了，在更广泛的“分数”颜色设置中，Hedetniemi的猜想也是对的。所谓的“分数”颜色，是指每个节点都可以分配到不同的颜色，例如2/3的黄色和1/3的绿色。这些发现都预示着Hedetniemi猜想可能是正确的。

但是也有人提出过反对意见。例如有数学家发现，对于需要无限多种颜色的图，或者对于每个连接都有一个偏好方向的有向图来说，Hedetniemi的猜想是不成立的。可Hedetniemi在提出这个猜想时设置的最初条件是：对有限的无向图进行无分数着色。数学家们似乎并不能在这样的设置下解决这个问题。

而Shitov用一个简明扼要的例子证明了Hedetniemi的猜想是错误的。

在他的证明中，他用到了“指数图”这个概念。什么是指数图？对于一个图来说，如果用固定数量的颜色对它进行着色，那么每一种着色方法都在它的指数图有一个对应的节点。这里指的着色方法包含的是所有的着色可能，并不仅限于两点之间必须用不同颜色的方法。如果图G中有7个节点，调色板中有5种颜色，那么指数图就有5⁷个节点。Shitov的第一步就是将图G和它的指数图结合起来形成张量积。

现在，返回到两个相邻节点需要用不同的颜色着色的要求上，我们无法确定调色板上的5种颜色足以为G着色；同样，它们可能也不足以给5⁷节点的指数图上色。但数学家们可以确定是，用这5种颜色，足以给由G和它的指数图构成的张量积着色。这是所有的指数图都具有的性质：由一张图和它的指数图结合起来建立的张量积，可以用与最初用来制作指数图的调色板完全相同的颜色数量来着色。

于是，Shitov通过展示如何构建这样一个图G，使G和它的指数图都需要比调色板中更多的颜色，反驳了Hedetniemi的猜想。在得知自己的猜想终于得到了解决后，Hedetniemi非常高兴，他称赞Shitov的证明优雅、简单、明确。

Shitov的图非常庞大，虽然具体的数字还没有计算出来，但他估计G图可能至少有4¹⁰⁰⁰⁰个节点，而指数图则至少有4¹⁰⁰⁰⁰个节点。这个数字甚至远远大于可观测宇宙中的粒子数量。不过在Shitov看来，这样的数字在数学证明中并不是没有先例，算不上极大，而且他的研究也没有排除存在更小反例的可能。

现在，数学家们已经知道Hedetniemi的猜想是错误的，那么下一个问题自然就是它错的程度有多大：与组成图相比，一个张量积所需的颜色要可以少多少，以及这样的反例能有多少节点和连接。在Shitov用仅仅两页纸的篇章证明了这个让无数数学家曾经跃跃欲试的问题之后，数学家将可以对这个问题继续加以推敲。

参考链接：

[1] https://www.quantamagazine.org/mathematician-disproves-hedetniemis-graph-theory-conjecture-20190617/

[2] https://arxiv.org/pdf/1905.02167.pdf

[3] www.sohu.com/a/321478881_136745

[4] https://k.sina.com.cn/article_6662194460_18d19051c00100nkmw.html

[5] http://k.sina.com.cn/article_2215881863_8413ac8700100j4da.html

[6] https://kuaibao.qq.com/s/20190618AZN1T200?refer=spider

[7] http://dy.163.com/v2/article/detail/EI06JVDF0511D3CN.html

3页纸能做什么？推翻一个数学猜想！ - sohu.com.pdf