53年历史的猜想被破解-数学家找到斯蒂芬·赫德涅米猜想反例

大家好，我是大老李，这期节目让我们在质数话题中插播一则新闻，它有关数学家在图论领域里的一个发现。在今年9月，俄罗斯数学家雅罗索夫·什托夫（Yaroslav Shitov ）发表了一篇仅三页的论文，论文中，其发现了一个有53年历史的图论领域中的猜想的反例，从而推翻推翻了这一猜想，这个猜想名为：斯蒂芬·赫德涅米猜想（Stephen Hedetniemi conjecture）。

要理解这个猜想，需要了解两个概念，图的“最小着色数”和图的“张量积”(Tensor Product)。这两个名词听上去很高大上，其实说清楚不难。

数学里的“图”就是一些点和一些连接点的线。这里点的位置，线的形状长度等等完全不考虑，只考虑点和线的连接关系。而两个点之间的连线称为“边”，两个点之间有一条边相连称为“相邻”。

（图论中的一张“图”：仅考虑点和连线关系）

图的着色问题，了解“四色定理”的听众应该也很熟悉了，就是对一幅图中的点进行着色，要求相邻的两个的两个点的颜色不同。“四色定理”是说对平面图，至多四种颜色着色就够了。“平面图”就是那种可以“摊平”，使得所有边可以不交叉的图，那种图，最多用四种颜色就可以着色，使相邻两点的颜色都不同，这就是“四色定理”。当然，对非平面图，你需要的颜色更多。

(“平面图”是那种没有边相交的图。上图中的左图是平面图，因其可以转化为右图，使得没有边相交)

“图的最小着色数”的意思就是，对一幅图最少需要几种颜色着色，可以使任何相邻两点的颜色不同，这个颜色种类数量，就是图的“最小着色数”。

再讲一下图的张量积，其实也不难理解，就是定义了一种两幅图的“乘法”，图与图乘起来得到另一张图。这种乘法的定义我们借助一道“应用题”来理解：

假设大老李要搞一次相亲会，大老李认识一些单身男性朋友。大老李的太太也认识一些单身女性朋友，所以大老李想把他们集中在一起，搞一次相亲会。

在相亲会中，大老李设计了一个游戏环节，是4人一组，两男两女参加。但是我知道我认识的那些男性朋友有些是互相认识的，我太太认识的女性朋友，有些也是互相认识的。游戏时，我希望参加的两位男士是互相认识的，两位女士也互相认识，这样玩游戏气氛更轻松热烈点。

到底我邀请的那些参加相亲会的朋友能否满足这样的分组条件呢？当然，这里假设参会的男女人数相等，而且都是偶数。

那这道题我可以这样解决，我先把参会的男性用一个点表示，两人如果相识则连一条线。这样得到一张男性朋友关系图。同样方法可以画出女性朋友关系图。

然后，我要参考这对两张图进行一个操作，得到一张新的图。操作方法如下：将所有男性朋友女性朋友可能两两组合，组成一对，在新的图中作为一个点表示，每个人可以重复组合出现。

比如，如果原来有a个男性和a个女性，那么根据简单的组合算法，新的图就会有a^2个点，每个点代表一对可能的组合。

然后，我要给这些点之间连线，连线规则是：取两个点，分别考察每个点所代表的组合对中的男性和女性。如果这两个男性和女性在原先的图中之间有连线，则把这两个点连一条线，否则不连线。举个例子就明白。

比如，如果我邀请参加相亲会的男性是哈利波特，罗恩，马尔福；女性方面是：赫敏，金妮，张秋。

(大老李邀请的男女朋友关系示意图)

那如果有一个点是表示的是哈利波特，金妮；另一个点表示的罗恩和赫敏，那么你需要把它们之间连条线，因为哈利波特和罗恩，以及赫敏与金妮算是好朋友。如果有一个点是表示的是哈利波特和张秋；另一个点表示马尔福和金妮，那么就不连线，因为哈利波特与马尔福肯定不是好朋友，张秋与金妮也没啥交集。总之，新的图中点要连线的话，要求就是在老的图中，对应点也有连线。

另外说明一点，自己与自己不需要连线，比如“哈利波特-赫敏”与“哈利波特-金妮”之间就不用连线了。

(根据前面的关系图求得的张量积图，它断开成了两部分)

以上我们就定义了一种从两张图进行一种组合，得到新的一张图的运算，数学里称这种运算叫“张量积”，听我这么一解释是不是也很简单。其实叫它“积”是有点道理的，至少你能看到新的图的点数是老的两张图的点数之积。

而对我来说，如果我能根据邀请来的男性和女性朋友关系图，求得一张张量积的图，那我知道，在这张张量积的图中，任意一条线段两端所代表的两男两女是适合才加这个相亲游戏的。当然，这个方法也许很笨，但至少说明了什么是图的张量积，后面我有时会简称为两张图的“积”。

另外，在数学中的张量积并不要求参与运算的两张图的点数相等。你也可以去分析张量积的一些性质，比如有没有交换律，结合律等等。但这都不重要，今天我们要考虑的是两张图的最小着色数与运算后所得的图的最小着色数的关系。

很早以前，数学家就证明了，两张图的积的最小着色数小于等于原先两张图的最小着色数的较小者。比如，如果原先两张图的最小着色数是4和5，则它们的积的最小着色数小于等于4。而很多人做了尝试，发现“小于”这种情况做不到 ，实验结果都是“等于”这种情况。

于是，1966年，当时还在读博士的斯蒂芬·赫德涅米，现为克莱姆森大学（位于美国卡罗莱纳州）教授，在其博士学位论文里作出了一个猜想：图的张量积的最小着色数等于原先两张图的最小着色数的最小者，后来被成为：斯蒂芬·赫德涅米猜想。

（斯蒂芬·赫德涅米猜想）

此后50多年里，数学家没能找出任何反例，倒是证明了一些比原猜想稍弱的命题，比如有人证明了，如果原先两张图中的其中一个的最小着色数小于等于4，则赫德涅米猜想是正确的。

但是这次，什托夫却找到了一个赫德涅米猜想的一个反例，即两个图的张量积的最小着色数比原先两个图都小。他的基本思路是利用了之前有关“幂图”的一个结论，幂是幂次的幂。就像之前介绍求张量积的运算，如果一个图G与自身求张量积，那么结果可以写成，类似可以有,等等。

但这类说的“幂图”里的运算，是另一种幂次。它的特点是底数和指数都是一个图。比如有图G,H，那么和都是一张图，都叫“幂图”(Exponential Graph)。幂图的定义略有点啰嗦，就不在音频里讲了。但是叫它幂图的肯定是有原因的。比如，如果图G有a个顶点，图H有b个顶点，那么这张图的顶点数就是。

Exponential Graph / 幂图 定义：

Given a definition below (source: On Hedetniemi's Conjecture and the color template scheme by C. Tardiff and X Zhu):

The exponential graph   has all the functions from vertex-set of 𝐻 to that of 𝐺 as vertices and two of these functions 𝑓, 𝑔  are joined by an edge if [𝑓(𝑢),𝑔(𝑣)∈𝐸(𝐺)] for all [𝑢,𝑣]∈𝐸(𝐻).

不管怎样，数学家之前已经证明，一个图 G与自己的幂图，比如构成的张量积，其最小着色数必须等于H的最小着色数。而Shitov构造了一个图G和它的幂图，使它们的最小着色数都大于H的最小着色数。而它们的张量积的最小着色数又等于H的最小着色数，所以这就构成了赫德涅米猜想的一个反例，从而推翻了这个猜想。

我知道你现在很想看看这个反例到底长啥样？很遗憾告诉你，这个反例画不出来，因为太大了。Shitov估计，这个反例的G的顶点数在左右，而它的幂图的点数在左右，所以完全不可能画出来，但是它确实可以在数学上用不到3页纸的篇幅，精确构造出来。

我觉得这是数学中有一个非常好的有关反例的例子。数学中有许多猜想，你可以找出许许多多实例代入验证，都是对的。但是，它却可以在非常非常遥远的位置出现一个反例，比如像这个猜想中，反例出现在的位置。

而今天图论我们也学了点，比如什么是图的张量积，也许你下次组织相亲活动的时候会相当图的张量积概念。好了，下期再见！

https://zh.wikipedia.org/zh-cn/%E5%BC%A0%E9%87%8F%E7%A7%AF

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

https://arxiv.org/abs/1905.02167

https://math.stackexchange.com/questions/524183/example-of-exponential-graph

https://en.wikipedia.org/wiki/Tensor_product_of_graphs#/media/File:Graph-tensor-product.svg