只用三頁紙，他推翻了困擾學界半世紀的重要猜想

圖片來源：Olena Shmahalo/Quanta Magazine

四色猜想是數學界最著名的猜想之一，即能否只用四種顏色給任意一張地圖上色。這一猜想已經被證明是正確的，但它的衍生問題仍然讓數學家著迷不已。最近，一位俄羅斯數學家發表了一篇僅有三頁的論文，推翻了該領域存在了 53 年的一個重要猜想。

撰文 | Erica Klarreich

翻譯 | 劉悅晨

審校 | 戚譯引

來源 | 科研圈（ID：keyanquan）

今年 5 月在線發表的一篇論文推翻了 53 年前提出的一個猜想，為圖著色問題提出了新的最優解。這篇論文僅僅三頁，卻證明了對於某些特定的網路而言，著色問題存在許多數學家沒有想到的更好的解法。

圖著色問題最早來源於人們在為地圖上色時的思考——最少使用多少種顏色，就能夠保證地圖中有相鄰邊界的國家或地區顏色不同？為了解決這一問題，數學家們鑽研了近 200 年。

這一問題可以被進一步簡化：將一張網路的每個節點染色，使得任意兩個相連節點顏色不同，最少需要多少種顏色？解決這個問題可以幫助我們更加高效地應對許多日常生活中的場景，例如如何在婚禮上為來賓安排座位，或如何為工廠安排不同時段的任務，甚至可以還用來解決數獨問題。

圖著色問題往往表述非常簡單，但是證明起來十分困難。即使是開啟了這一領域的問題，即能否只用四種顏色就能給任何一張地圖上色，保證兩個相鄰的區域顏色各不相同，也歷經了一個世紀的求解。（答案是能，如果你想知道的話。）

這篇最新發表的論文也沒有推翻「四色規則」，卻提出了一種更好的解法。這一問題之所以 50 多年來一直都未能被解決，是因為它涉及到了複雜的張量積（tensor product）問題，即由兩個不同的圖形（圖論中將其稱為 G 和 H）以特定的方式組成的新圖形。G 和 H 的張量積是一個更大的新圖形，其中每一個節點都代表了來原始圖形中的一對節點，分別來自 G 和於 H；並且，如果張量積中的兩個節點在 G 中對應的節點和在 H 中對應的節點都是相連的，那麼它們也是相連的。

設想一下，如果你是一名音樂老師，你想為五年級孩子們的音樂會找到好的二重奏組合。你便可以繪製這樣的兩幅圖：一幅圖中，用不同的點代表不同的學生，點與點之間的連接代表兩個學生相處融洽、可以配對；另一幅圖中，用不同的點代表不同的樂器，點與點之間的連接代表二重奏樂譜中包括有這兩件樂器的樂譜。那麼，這兩幅圖的張量積中所包含的點則代表一名學生及其會演奏的一種樂器，如果張量積中的兩個點相連，則意味著兩名學生能相處得很好，樂器的種類也能搭檔，可以組成二重奏。

1966 年，現為克萊姆森大學教授的 Stephen Hedetniemi 在他的博士論文中提出，填充張量積時需要的最少顏色數量與填充組成它的兩張圖時需要的顏色數量較少的那張相同。「這是圖論當中一個非常重要的假設。」耶路撒冷希伯來大學的 Gil Kalai 說，「許多研究者們都思考過這個問題。」

幾十年以來，數學家積累了一系列有關這一猜想的研究證據，其中一些表明它是正確的，而另一些則認為它是錯誤的。儘管數學家們對於這個猜想的正確與否各執一詞，但似乎每個人都同意，無論是證明還是證偽都非常困難。

「我個人認為這個猜想應該是真的，因為很多聰明的人都研究過它，如果有的話，應該早能夠找到一個反例。」多倫多瑞爾森大學的 Anthony Bonato 說。

但現在，俄羅斯數學家Yaroslav Shitov提出了一種簡單的方法來構建反例：填充張量積需要的顏色比填充兩個組成圖時需要的顏色都要少。加拿大本拿比西蒙弗雷澤大學的 Pavol Hell 認為，這一方法「雖然簡單，卻十分巧妙」。

Hell 指出，張量積與不同圖形之間應該如何相互映射的問題密切相關。在數學領域，Hedetniemi 的猜想可能是最大的開放問題之一，「這篇論文的發表是一個重要的突破」。

Yaroslav Shitov 找到了一個反例，推翻了 Hedetniemi 在 53 年前提出的猜想。圖片來源：?zde Bayer, Max Planck Institute for Mathematics in the Sciences

色彩斑斕的聚會

為了更好地理解可以用著色張量積的思維方式解決怎樣的現實問題，請想像這樣一種情形：你計劃在幾個周末邀請不同的朋友到你的鄉村莊園聚會，作為一名細心的主人，你希望將那些有共同話題的人聚集在一起。

你知道你的一些朋友有工作，他們可以立即建立聯繫，但另外一些人卻沒有。同樣，你知道每個朋友都有一個愛好，因此客人們可能會通過聚會找到分享他們興趣和愛好的對象。你希望在每一次聚會中，每兩位客人之間都能夠找到一些共同語言，無論是在工作方面，還是在興趣愛好方面；並且你想知道一共需要組織多少次聚會，才能邀請完列表中的所有人。

你可以用一張圖來表示不同工作之間的關係，不同的點代表工作，點之間的連接代表兩個工作之間沒有共同話題。（這聽起來好像標反了，但是這樣的連接方式在圖著色問題中是有意義的，因為我們最終需要用顏色來區分有問題的配對方式。）同樣地，你可以用另一張圖來表示不同興趣愛好之間的關係，點之間的連接代表兩個興趣愛好之間不存在共同話題。

這兩個圖的張量積將為每個工作-愛好配對提供一個節點，如果兩個工作和兩個愛好都不存在共同的話題，則兩個節點相連——這正是你希望在聚會時避免發生的情況。

現在，你可以為張量積的節點著色，使得相互連接的節點具有不同的顏色，從而得到一份在不同周末組織聚會的訪客列表。你可以在「綠色」周末邀請綠色節點對應的朋友，「紅色」周末邀請紅色節點對應的朋友，以此類推，從而確保沒有共同話題的客人將在不同的周末參加聚會。所使用的顏色數量可以告訴你在日曆中需要被預留的周末的數量。

從這個例子中可以注意到的是，在與工作相關的圖形中，任何有效著色都會延伸到張量積——在著色時，可以簡單地將每個工作-愛好組合的節點直接用工作對應的顏色著色。如果根據這種著色方法組織聚會，那麼每對客人將完全基於他們共同的職業興趣進行交談，無論他們的愛好如何。同樣地，任何在興趣圖中的著色方式也可以延伸到整個張量積的圖中。Hedetniemi 猜想，在兩張圖的著色方法中，使用顏色較少的是為張量積著色的最佳方法。

從表面上看，Hedetniemi 的猜想似乎不太可信。畢竟，如果你基於工作圖的著色進行張量積的著色，就得忽略朋友們之間存在的共同愛好，那些本來非常合適在一起聚會的客人可能就會被分開。反之，如果你把所有關於工作和愛好的信息結合起來，你或許就能用更少的顏色來預留周末安排聚會，為自己留出多一些清凈的周末時光。

然而，五十多年來，數學家們仍然找不到任何一種張量積圖形，可以用比組成它的兩個圖都要少的顏色來填充。他們發現，只要兩個組成圖中的一個著色時需要四種或更少的顏色，Hedetniemi 的猜想就是正確的。在更廣泛的「分數」著色中也是如此，即每個節點可以分配一個顏色組合，例如 2/3 黃色和 1/3 綠色。（就上文提到的周末家庭聚會的例子而言，這相當於你有三個會打網球的記者朋友，你在標記為「黃色」的周末邀請其中兩位，在標記為「綠色」的周末再邀請第三位。）

這些證據表明 Hedetniemi 的猜想可能是正確的，但也有證據指向了相反的方向。例如，數學家已經證明，對於需要無限多種顏色的圖形或者是有向圖（即其中的每個連接都有一個偏好的方向），Hedetniemi 的猜想將不再適用。但是，即使數學家在一些更廣泛的場景下證明了 Hedetniemi 的猜想，在另一些場景下又推翻了猜想，他們也似乎無法在 Hedetniemi 最初考慮的情形下解決它，即具有非分數著色的有限無向圖。

終結爭議

現在，Shitov 通過一個清晰、簡單的證明終結了這些爭議，證明 Hedetniemi 的猜想是錯誤的。在那篇研究論文中，他僅用了略多於一頁密集的數學論證，便展示了如何構造一個張量積反例，使得填充它所需要的顏色比填充其任何一張組成圖所需要的顏色都要少。

Shitov 首先考慮將圖 G 與它的指數圖之一組合形成張量積的情況。用固定數量的顏色對 G 著色，每一種可能的情況在指數圖中對應一個節點（這裡允許每種可能的著色，而不僅僅是相互連接的節點著色不同的情況）。例如，如果圖形 G 具有 7 個節點，而著色板中有 5 種顏色，那麼指數圖將有有 57個節點，「指數圖」的名字也由此而來。

接下來，看看相連節點顏色不同的著色方式。我們無法保證調色板中的 5 種顏色足以使圖 G 著色；同樣，它們可能也不足以給有 57個節點的指數圖著色。但是數學家早就知道有一張圖，用這 5 種顏色就可以完成著色——G 和它的指數圖生成的張量積。

事實上，所有指數圖都具有以下屬性：要給一張圖及其指數圖的張量積著色，使用的顏色數量可以等於生成指數圖所需的顏色數量。Shitov 展示了如何構建一個圖 G，使得 G 及其指數圖都需要比張量積圖中更多的顏色進行著色，從而反駁了 Hedetniemi 的猜想。

Stephen Hedetniemi 的猜想近半個世紀後終於被推翻。圖片來源：Courtesy of Stephen Hedetniemi

Hedetniemi 的猜想歷時幾十年終於被推翻，他本人表示對此感到「非常高興」。Shitov 的證據「具備一定的優雅和簡潔，而且絕對優質，」他在一封電子郵件中寫道。還有數學家認為，Shitov 舉出的反例是聰明且有創造力的，它不需要任何複雜的、尖端的數學工具。「對圖論的研究者而言，你可以用兩句話解釋它的構造，」Kalai 說。

至於為什麼這樣的論點一直被忽視了超過 50 年，這對於數學家們來說還是一個謎。「有時，一塊小寶石常會被樹葉覆蓋，」Hell 說，「Shitov 只是設法比任何人都更深刻地理解它。」

Shitov 論文中舉例的圖非常龐大：雖然他沒有精確計算它們的大小，但他估計圖 G 可能至少有 4100個節點，而指數圖至少有 410000個節點——這個數字遠遠大於可觀測的宇宙中所有粒子的估計數量。

然而，「龐大」只存在於旁觀者的眼中。對於 Shitov 來說，這次提出的反例「並不是非常巨大」。他說：「在數學研究中存在一些更大的反例，相比之下這個只是非常微小的一個。」雖然你不太可能邀請到 410000位客人到你的鄉村別墅進行聚會，但 Shitov 的工作並沒有排除存在更小反例的可能。

如今，既然數學家知道 Hedetniemi 的猜想是錯誤的，那麼自然地，下一個問題就是它到底錯到什麼程度——張量積需要的顏色可能比其組成圖要少多少？這些反例的節點和連接數量最少是多少？

Alon 指出，這篇論文給數學家們提供了一個重要的教訓：「有時候，一個猜想很難被證明，可能僅僅是因為它是錯誤的。」

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

來源：科研圈

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