一位俄羅斯數學家提出了一種更好的方式來為網路圖著色

摘要：既然數學家們已經知道史蒂芬的猜想是錯誤的，那麼下一個自然的問題就是它有多錯誤：一個張量積可能比它的組成圖少多少種顏色，以及這樣的反例能有多少節點和鏈接。例如，數學家們已經證明，斯蒂芬的猜想對於需要無限多種顏色的圖或者對於每個鏈接都有一個首選方向的矢量圖來說是不成立的。

上個月在網上發表的一篇論文駁斥了53年前的一個猜想，即給網路節點分配顏色的最佳方式。這篇論文僅用三頁紙就展示更好的方法來給網路圖上色。

網路圖著色問題是近200年來數學家們研究的一個熱點問題，它的靈感來自於如何將相鄰區域的顏色映射成不同的顏色。目標是弄清楚如何給某些網路的節點上色，這樣就不會有兩個連接的節點「共享」相同的顏色。根據具體情況，網路著色可思想可以用來安排如何讓客人在婚禮上就座，可以安排工廠任務，甚至解決數獨難題。

圖的著色問題往往易於表述，但往往很難解決。四種顏色是否足以為任何圖形著色？

直到現在，這篇新論文所處理的問題似乎也不例外。它涉及張量積——由兩種不同的圖(稱為G和H)以特定的方式組合而成的圖。G和H的張量積是一個新的、更大的圖中，其中每個節點代表原始圖中的一對節點，一個來自G，一個來自H，並且張量積中的兩個節點都連接在一起。

假設你是一位音樂老師，想為五年級的音樂會找到一對好的二重唱組合。您可以製作一個以學生為節點的圖表，並在每一對相處得很好的學生之間建立鏈接。如果你有兩種樂器之間的連接，如果你有以它們為特色的二重唱樂譜，那麼你可以製作第二個圖表，其中每個節點都是不同的樂器。這兩個圖的張量積對於一個學生和一個樂器的每一個可能的配對都有一個節點，只要兩個學生在一起工作得很好，而且這兩個樂器兼容，兩個節點就會連接起來。

斯蒂芬在他的博士論文中推測，張量積所需的最小顏色數與其兩個構成圖之一所需的顏色數相同 。這是圖論中的一個主要猜想。」

幾十年來，數學家們積累了大量的證據，其中一些證據表明這個猜想是正確的，另一些則是錯誤的。對於哪種可能性最終會占上風，數學家們有不同的猜測。但至少每個人似乎都同意，這個問題很難解決。

多倫多瑞爾森大學的安東尼博納托表示：「我個人認為，這個猜想應該是正確的，因為很多聰明人都看過這個猜想，如果存在的話，他們應該已經找到了一個反例。」

但現在，俄羅斯數學家雅羅斯拉夫提出了一種構造這種反例的簡單方法：張量積需要的顏色比兩種構成圖中的任何一種都少。這個證明「很簡單，但很巧妙」。

張量圖與不同的圖之間如何映射的問題密切相關，在數學領域，斯蒂芬的猜想可能是最大的開放問題，這是一個重要的突破。

五顏六色的聚會

為了對你能從一張張量圖上色中收集到的信息有所了解，想像一下你計劃邀請朋友到你的鄉村莊園度過一系列的周末。作為一個好的主人，你想要聚集那些喜歡彼此陪伴的人。

你知道，你的一些朋友有同樣工作，他們可以立即聯繫。同樣，你知道每個朋友都有自己的愛好，這也是客人們發現共同興趣的另一種方式。你想，會拉大提琴的舞蹈老師可能喜歡和會打網球的瑜伽教練談笑風生，但可能很難和集郵的政治科學家交談。你希望參加任何聚會的每一對客人都能找到一些共同感興趣的領域，無論是通過工作還是愛好，你想知道在邀請名單上的每一個人之前，你需要舉辦多少次聚會。

雅羅斯拉夫發現了一個與斯蒂芬提出的已有53年歷史的圖論猜想相反的例子。您可以使用節點為作業的圖來表示不同作業之間的關係，並使用鏈接連接任何兩個不利於共享業務對話的作業。同樣，您可以製作一個節點是不同愛好的圖表，並在兩個愛好不兼容時將它們連接起來。

這兩張圖的張量積將為每個工作—愛好配對有一個節點，如果兩個工作和兩個愛好都不相容，兩個節點就會連接起來——這正是你在周末請客時想要避免的情況。現在，您可以為張量的節點著色以使連接的節點具有不同的顏色，那麼將為您提供一種方法來形成不同周末的訪客列表：您可以在「綠色」周末邀請與綠色節點對應的人員，「紅色」周末邀請與紅色節點對應的人等，保證不相容的客人將在不同的周末訪問。您使用的顏色數量可以告訴您日曆中要「關閉」的周末數量。

從這個例子中需要注意的一件事是，任何工作圖的有效著色都可以延續到張量積——你可以使用的相同顏色簡單地將每個工作愛好的顏色組合到他們的工作中。這樣的色彩可以很好的安排聚會，每一對客人都是完全基於他們共同的職業興趣。

從表面上看，斯蒂芬的推測似乎不太可能。畢竟，如果你把你的張量著色建立在工作圖的著色基礎上，你就忽略了你所知道的關於你朋友的兼容愛好的所有事情，並且有可能把本來可以相處得很好的客人分開。相反，如果你把你所有關於工作和愛好的信息結合起來，也許你可以少用一些顏色，享受一些應得的免費周末。

然而，在50多年的時間里，數學家們找不到一個張量積比它的兩個組成圖中的顏色更少。在更廣泛的「分數」顏色設置中也是如此，在這種情況下，每個節點都可以分配一組顏色——可能是2/3黃色和1/3綠色。(就周末家庭聚會而言，這可能相當於有三個不同的朋友打網球，邀請其中兩個在「黃色」周末，第三個在「綠色」周末。)

這些發現暗示了這個猜想可能是正確的，但是其他的發現卻提出了相反的觀點。例如，數學家們已經證明，斯蒂芬的猜想對於需要無限多種顏色的圖或者對於每個鏈接都有一個首選方向的矢量圖來說是不成立的。但是，即使數學家們在一些更廣泛的背景下證明了斯蒂芬的猜想，並在另一些更廣泛的背景下證明了它的錯誤，他們似乎也無法在斯蒂芬最初考慮的設置中解決它：有限的、無向的、帶有非分色的圖。

普林斯頓大學的Noga Alon說:「人們普遍認為這很可能是真的，但無論如何，這是非常困難的。」

著色頁面

雅羅斯拉夫現在用一個清晰、簡單的例子，從這些不確定性中找到答案，證明斯蒂芬猜想是錯誤的。在一篇論文中，他展示了如何構造一種張量積，這種張量積所需的顏色比它的任何一個組成圖都要少。

雅羅斯拉夫首先考慮當把一個圖G和它的一個「指數」圖結合起來形成一個張量積時會發生什麼。一個指數圖對於G的每一種可能的顏色都有一個節點，每個節點都有固定數量的顏色(這里，我們允許每一種可能的顏色，而不只是連接節點的顏色不同)。如果圖G有7個節點，而調色板有5種顏色，那麼指數圖就有5^7個節點——因此得名「指數圖」。

斯蒂芬·海德涅米關於兩張圖的張量積所需要的最小顏色數的猜想，半個多世紀以來一直沒有得到解答。將我們的注意力返回到顏色上，其中連接的節點應該是不同的顏色，我們不能保證調色板中的五種顏色足以為圖G著色;同樣，它們可能也不足以給57節點的指數圖上色。但數學家們早就知道，有一個圖形，這五種顏色足以著色:由G和它的指數圖構成的張量積。

事實上，所有的指數圖都有這樣的性質：把指數圖和它所建立的圖結合起來的張量積可以用與最初用來製作指數圖的調色板完全相同的顏色來著色。雅羅斯拉夫通過展示如何構建一個圖G來反駁史蒂芬的猜想，使得G和它的指數圖都需要比調色板中更多的顏色。

史蒂芬宣稱自己「非常高興」自己的猜想在這麼多年後得到了解決。希托夫在一封電子郵件中寫道，他的證明「具有某種優雅、簡單和明確的品質」。

數學家們說，這個新的反例很聰明，很有創意，不需要任何複雜、前沿的數學工具。「對於圖理論家來說，你可以用兩句話來解釋這個結構，」卡萊說。

為什麼這樣的論點被忽視了50多年對數學家來說是一個謎。「有時候，一小塊寶石會被樹葉覆蓋，」黑爾說。「他只是比任何人都更深刻地理解了這一點。」

雅羅斯拉夫的圖是巨大的：雖然他沒有精確計算出它們有多大，但他可能G圖可能至少有4^100個節點，而指數圖至少有4^10000個節點——這個數字遠遠大於可觀測宇宙中粒子的可能數量。

再說一次，「巨量」是在旁觀者的眼中。對於雅羅斯拉夫來說，他的反例「不是特別大」.他說。「在數學領域也有反例(與之相比)，這確實是一件小事。」

雖然你不可能邀請4^100名客人到你的鄉間別墅做客，但雅羅斯拉夫的研究並沒有排除存在更小的反例。既然數學家們已經知道史蒂芬的猜想是錯誤的，那麼下一個自然的問題就是它有多錯誤：一個張量積可能比它的組成圖少多少種顏色，以及這樣的反例能有多少節點和鏈接。

同時，這篇新論文給數學家上了重要的一課。有時候，一個猜想很難被證明的原因很簡單，那就是它是錯誤的。

>一位俄羅斯數學家提出了一種更好的方法來為網路圖著色