Hedetniemi 猜想被否定


cached-thumb-img.32269.0.998742074225433.png

2019-5-6,Yaroslav Shitov( https://www.hse.ru/en/org/persons/61713553 )在 arXiv 上贴出一篇两页半论文(其中一页是问题背景介绍和定义), Counterexamples To Hedetniemi’s Conjecture (arXiv:1905.02167v1),构造出 Hedetniemi 猜想的反例。多位学者 (包括我自己) 仔细检查了证明,相信 Hedetniemi 猜想已被否定。

Hedetniemi 猜想:对任意图 G,H,\(\chi\)(G\(\times\) H) = min {\(\chi\)(G),\(\chi\)(H)}。

该猜想 1966 年提出,发表在一个 Technique report 上。当时并没有引起注意。1976 年,Burr-Erdos-Lovasz 研究图的 Ramsey 色数。提出一个有关 Ramsey 色数的猜想。他们证明 Hedetniemi 猜想蕴含了该猜想。至此以后,Hedetniemi 猜想广受重视。有的地方称之为乘积图染色猜想,或者 Hedetniemi-Lovasz 乘积图染色猜想。陆续有四篇综述性论文发表(其中一篇是我于 1998 年发表的)。一些特殊情形被证明。最好的结果应该是我的博士导师 Norbert Sauer 和他的学生 El-Zahar 证明的结果:当 min {\(\chi\)(G),\(\chi\)(H)}=4 时,猜想成立。另外,我在 2011 年证明了该猜想的分数形式成立,由此可推导出 Burr-Erdos-Lovasz 有关 Ramsey 色数的猜想。

Hedetniemi 猜想,命题如此简洁美丽,我原把它看作是在图的染色中仅次于 Hadwiger 猜想的问题,一直以为应该成立。但是,它是个美丽的错误命题。而且反例仅用一页半给出,出乎预料。不过,由该猜想导出的一系列问题的研究应该还会继续。

Yaroslav Shitov,我原来并不知道这个名字。看了这篇论文后,惊叹于论文中精妙的想法,对这个人好奇,查了一下。

2012 年,Lomonosov Moscow State University 博士毕业。

博士论文: Rank functions for matrices over semirings

已发表论文 50 多篇。大多是代数矩阵方面的论文。大多论文的内容我不熟悉。有一篇今年 1 月 19 日在 arXiv 上贴出的论文 arXiv:1901.06542 与 Cerny 猜想(http://u.cs.biu.ac.il/~trakht/syn.html )相关。该猜想我略有了解。Cerny 猜想是一个比 Hedetniemi 猜想更早一点(1964 年以前)的猜想。是关于可同步有限自动机(synchronizing finite automoton) 的重设语句长度(length of the shortest rank-one words)的猜想。若干年前,一位数学家解决了一个图的路径染色猜想,上了社会新闻。有点尴尬是我虽然一直做图的染色问题,但是当时并不知道该猜想是什么。后来了解了一下,该猜想源于可同步有限自动机的研究,可表示为有向图的边的标号问题。相关的另一个更著名的猜想是 Cerny 猜想。可表述为矩阵问题和有向图问题。除了研究有限自动机的人外,很多研究矩阵的人在研究该问题。

Cerny 猜想:任意一个有 n 个状态的可同步有限自动机 A 的最短重设语句长度 \(\text {rt}\left (A \right) \leq \left (n-1 \right)^{2}\)。

1982-83, Pin-Frankl 证明 \(\text {rt}\left (n \right) \leq \frac {1}{6} n^{3} + o\left (n^{3} \right)\)。虽然研究者众,这一结果 35 年后才有人将系数 \(\frac {1}{6} = 0.1666\ldots\) 改进为 0.1664。Shitov 的上述论文将该系数改进为 0.1654。\(n^{3}\) 是一个难以撼动的级别。

Shitov 的论文惜字如金,证明叙述精准,吝啬。不多写一个字。原以为两页半论文超短,一看他有好几篇一页的论文。最短的小半页,主文 9 行。我写 email 向他请教一个问题,他寄来上述 arXiv 论文的改进版,又少了 6 行(论文中,除去问题背景介绍和已有的定义,证明部分也就五十多行)。结果更好一点。所造的反例图小一些。不过反例图的大小不太好估计,原来图的顶点数也许在 \({2^{10}}^{10}\) 级别,新的图也许在 \({2^{10}}^{6}\) 级别。原来的证明有两个重要的 Claims 加上一个定理。现在两个 Claims 变成一个 Claim,原来的定理变成另一个 Claim。

2012 年博士毕业(https://www.genealogy.math.ndsu.nodak.edu/id.php?id=170670 ),精力正旺,早上八、九点钟的太阳。

作者: 朱绪鼎,浙江师范大学教授