3頁紙能做什麼？推翻一個數學猜想！

授權轉自：原理

哲學園鳴謝

Yaroslav Shitov是一名俄羅斯的數學家，上個月，他在arXiv發表了一篇論文，在這篇只有3頁長（主體部分僅有2頁）的論文中，他推翻了數學家Stephen Hedetniemi在1966年提出的一個猜想。這是一個在圖論中非常重要的猜想，幾十年來，不斷有數學家想要嘗試解開這個難題，卻一直無人能夠判斷它究竟是對是錯，直到現在……

1.

在介紹Hedetniemi的猜想之前，我們先要介紹的是另一個數學家們已經研究了200多年的熱點問題，那就是如何在地圖上給相鄰的國家塗上不同的顏色。這一類問題啟發了很多類似的數學研究，他們或許看起來容易，但解起來卻非常難。這一領域中的四色地圖問題便是這樣一個猜想：用4種顏色足以給任何一張地圖上色嗎？數學家花了一個多世紀的時間，終於得到了肯定的答案。

數學家從地圖著色問題中受到啟發，繼而開始探索網路（或者說「圖」）中的節點著色問題。他們的目標是要弄清楚如何給圖中的節點著上顏色，使得兩個相連的節點顏色不一樣。

這個問題與兩個張量的張量積有關。張量積是兩個不同的圖（G和H）以某種特定的方式組合而成的更新、更大的圖。在新的圖中，每個節點代表著一對來自原始圖的節點——一個來自G、一個來自H，而且如果兩個在張量積中的節點是相連的，那麼它們在H、G上的相應節點就也是相連的。

我們可以舉個例子來解釋它的意思。假設你是一名音樂老師，需要找兩名學生來表演一場二重奏，你需要他們滿足兩個條件，一是能良好相處，二是演奏的樂器能夠配合一場二重奏演出，那麼你就可以製作兩張圖表：第一張圖以學生為節點，將每一對合得來的學生連接起來；第二張圖以樂器為節點，將所有可以組成二重奏的樂器兩兩相連。對於每一個學生和一種樂器的組合，在張量積中都會有一個節點，例如A對長號、B對小提琴。如此一來，當出現兩個學生相處良好，且他們的樂器也可以配合演奏時，這兩個節點就會連接起來。

53年前，Hedetniemi在他的博士論文中提出猜想：一個張量積所需的最少顏色數量，與組成它的兩張圖中需要顏色數量較小的那張相同。這麼多年來，數學家們積累了很多與它有關的研究，有人相信它是正確的，有人覺得它不對。但如果它是錯的，又沒人能提供一個可以有效駁斥這個猜想的反例。

直到Shitov想出了一種簡單而精妙的方法，成功地構造出了一個反例：張量積所需要的顏色數量比兩種構成圖中的任何一種都少。

2.

一張張量圖的著色，能告訴我們什麼呢？我們可以舉個例子：假設你要在一連好幾周的周末都安排一些人前往某個地方度假，你需要以他們的職業和愛好為依據，讓每個前往度假的人無論是通過職業還是愛好，都能找到與他有共同興趣的人，然後將這些人安排到同一個周末。

張量圖的著色問能有效地幫助你處理這個問題，並能計算出需要多少個這樣的周末才能安排完所有前去度假的人。

首先你要製作一張以職業為節點的圖表，然後將那些不利於對話交流的工作連接起來；接著，再製作一張以愛好為節點的圖，也將兩個衝突或者說不兼容的愛好連接起來。

這兩張圖的張量積將為每個工作-愛好的配對生成一個節點，它連接的是兩個在工作和愛好上都不相容的節點，也就是你需要在安排時避免的情況。接著，你可以對張量積的節點著色，給相連的節點著上不同的顏色。然後，再將顏色相同的節點所對應的人安排到一起，並且根據使用了的顏色數量，決定需要多少個周末。

這時候你可能會注意到，在職業節點圖中的任何有效著色，都可以延續到張量積中。因此，你可以簡單地將職業節點圖中的著色運用到到張量積中的每個工作-愛好組合的著色中。這樣一來，聚會中的每一對客人都是完全基於他們在職業上的興趣，而非愛好上的興趣而聚集在一起的。反之亦然。

Hedetniemi的猜想說明的是，這兩張圖中使用顏色更少的一種，是給張量圖上色的最好方法。表面上看來，Hedetniemi的猜想似乎不太可行，因為如果張量圖的著色是建立在職業圖的著色基礎上，那麼所有關於愛好兼容性的信息就被全部忽略了，並且有可能會把原本可以相處愉快的人給分隔開了。但是，如果把所有關於職業和愛好的信息都結合起來，或許有可能少用一些顏色，用更少的周末就安排完了所有的人。

50多年來，數學家們一直沒能找到一個所需顏色數量比組成圖所需的顏色數量更少的張量積。1985年，數學家Mohamed El-Zahar和Norbert Sauer證明了當兩個組成圖中的其中一個所需顏色為4種或更少時，這個猜想是正確的。2011年，數學家朱緒鼎發表論文的證明了，在更廣泛的「分數」顏色設置中，Hedetniemi的猜想也是對的。所謂的「分數」顏色，是指每個節點都可以分配到不同的顏色，例如2/3的黃色和1/3的綠色。這些發現都預示著Hedetniemi猜想可能是正確的。

但是也有人提出過反對意見。例如有數學家發現，對於需要無限多種顏色的圖，或者對於每個連接都有一個偏好方向的有向圖來說，Hedetniemi的猜想是不成立的。可Hedetniemi在提出這個猜想時設置的最初條件是：對有限的無向圖進行無分數著色。數學家們似乎並不能在這樣的設置下解決這個問題。

3.

而Shitov用一個簡明扼要的例子證明了Hedetniemi的猜想是錯誤的。

在他的證明中，他用到了「指數圖」這個概念。什麼是指數圖？對於一個圖來說，如果用固定數量的顏色對它進行著色，那麼每一種著色方法都在它的指數圖有一個對應的節點。這裡指的著色方法包含的是所有的著色可能，並不僅限於兩點之間必須用不同顏色的方法。如果圖G中有7個節點，調色板中有5種顏色，那麼指數圖就有5?個節點。Shitov的第一步就是將圖G和它的指數圖結合起來形成張量積。

現在，返回到兩個相鄰節點需要用不同的顏色著色的要求上，我們無法確定調色板上的5種顏色足以為G著色；同樣，它們可能也不足以給5?節點的指數圖上色。但數學家們可以確定是，用這5種顏色，足以給由G和它的指數圖構成的張量積著色。這是所有的指數圖都具有的性質：由一張圖和它的指數圖結合起來建立的張量積，可以用與最初用來製作指數圖的調色板完全相同的顏色數量來著色。

於是，Shitov通過展示如何構建這樣一個圖G，使G和它的指數圖都需要比調色板中更多的顏色，反駁了Hedetniemi的猜想。在得知自己的猜想終於得到了解決後，Hedetniemi非常高興，他稱讚Shitov的證明優雅、簡單、明確。

Shitov的圖非常龐大，雖然具體的數字還沒有計算出來，但他估計G圖可能至少有41??個節點，而指數圖則至少有41????個節點。這個數字甚至遠遠大於可觀測宇宙中的粒子數量。不過在Shitov看來，這樣的數字在數學證明中並不是沒有先例，算不上極大，而且他的研究也沒有排除存在更小反例的可能。

現在，數學家們已經知道Hedetniemi的猜想是錯誤的，那麼下一個問題自然就是它錯的程度有多大：與組成圖相比，一個張量積所需的顏色要可以少多少，以及這樣的反例能有多少節點和連接。在Shitov用僅僅兩頁紙的篇章證明了這個讓無數數學家曾經躍躍欲試的問題之後，數學家將可以對這個問題繼續加以推敲。

參考鏈接：

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

https://arxiv.org/pdf/1905.02167.pdf

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！