張貼日期：Oct 01, 2018 10:18:20 AM

Hadwiger-Nelson 問題

圖論 (Graph Theory) 是眾多數學領域中，專門研究一群物件與物件彼此關聯的學問。

將要研究的對象物件以頂點視之，兩個物件若有關聯則連接一條邊，圖論主要是研究這個抽象化後由 (頂點集, 邊集) 所構成的圖之性質。著色問題可以說是圖論最經典的研究主題之一，透過著色，我們可以將圖分類，這個是可以 2 著色的圖，那個是可以 5 著色的圖…。如果有人問你數學家都在做什麼工作？有一個我認為還不錯又簡單的答案，那就是「分類」。各種領域的數學家都在忙著分類。而〈著色數〉是圖的一項重要分類指標。

1950 年，就讀芝加哥大學的大學生愛德華·尼爾森 (Edward Nelson) 提出了這樣一個著色問題:

在二維平面上，任意選一些頂點，如果頂點間的距離是1個單位，就把這兩頂點連接一條邊。這種圖稱為單位距離圖 (unit-distance graph)。尼爾森好奇平面上隨便一個這樣子的圖，〈點著色數〉是多少呢？

〈點著色〉要求將圖的所有頂點著色，且彼此有邊的頂點必須要塗不同色。一個圖的〈點著色數〉就是滿足上述要求的方法中使用最少的顏色數。

如果把平面上無限多個點都當成頂點，這個擁有無窮多個頂點和無窮多條邊的圖的點著色數是多少呢？這就是困擾圖論專家一甲子的《Hadwiger-Nelson 問題》。

當然，這個問題之所以有名並不是因為提出者尼爾森，而是後來正式寫下來刊載在《科學美國人》的已故數學科普大師馬丁·葛登能 (Martin Gardner) ，葛老爹的文章除了吸引不少業餘數學愛好者的目光，也引起不少知名圖論專家的興趣，其中包括了赫赫有名的保羅·艾狄胥 (Paul Erdős)，即便如此，集結眾人之力還是沒能解開這道難題。不過，也不是無功而返，數學家們很快地就將這個涉及到無窮圖的難題的正確答案，限縮到一個乍看不可思議的小範圍－介於４到７之間。

「開玩笑吧？！一個無窮多個頂點和邊的圖，這麼複雜的圖居然只要最多７色就能夠完成點著色。」我想許多讀者心裡會有這樣的ＯＳ，事實就是如此，真相稍後揭曉。

有趣到連生物學家也來湊一咖

截至今日，正確答案雖然還沒人知道，但是，就在今年四月，奧伯利·迪·格雷 (Aubrey de Grey) 丟了一篇論文證明：四個顏色不夠用。讓正確答案的範圍又縮小了，只剩下 5, 6, 7 三種可能。不過，別小看他這一手，雖然看似輕鬆，其實困了眾多數學家六十年啊!

比較令人感到驚奇的是，突破僵局的格雷教授並不是專門搞數學的，他的身份是一位致力於長生不老的生物學家，某天在玩棋盤遊戲時突發奇想突破了難關。

在此之前，格雷有一項著名事蹟廣為人知，他主張「老化是一種疾病」，只要掌握住關鍵的幾個要素，就能夠抗老，預言人類未來將可以活到一千歲，而且第一個活到一千歲的人已經誕生在世界上了。不論你信不信，我個人希望這件事不要成真，不然五十代同堂可不得了，光是過年吃個年夜飯，連洗碗都有問題啊啊啊！不過，跟秦始皇一樣對於長生不老有興趣的讀者還是可以到 TED TALK 網站觀看他的演講《A roadmap to end aging》。

為什麼無限多個點只要有限個顏色就足夠了

其實９色就可以順利完成了。

理由很簡單，考慮一個邊長 2/3 單位的正方形，最遠的兩點落在對角線的兩個頂點上，簡單利用畢氏定理知道對角線長度不足 1 單位，因此，整個正方形可以塗單一色。接著用９個不同顏色的同尺寸正方形，排成九宮格。

再重複把這九宮格平移貼上，規律地鋪滿整個平面就完成了。檢查一下：看看是不是任意一個點，跟距離它 1 單位的點都塗不同色呢？

六十年前 7 色的塗法採用類似的概念，只不過用「正六邊形」取代「正方形」來鋪滿整個平面，中間一個加上外圍六個不同色的正六邊形，就是 7 色的塗法。

至少需要 4 色的理由

首先畫兩個單位圓通過彼此的圓心，則兩圓心距離為 1，且兩交點距離圓心也是 1，因此光這四個頂點至少要用掉三個顏色才行。

複製中間這個菱形，將兩個菱形的上頂點釘在一起，分別向左右兩邊旋轉，直到下頂點彼此距離為 1 時停止，此時，兩個下頂點的顏色也被迫要相異，因此三個顏色已經不夠用了，不得已只好使用第四個顏色。這個 7 頂點的圖是需要四色的最小範例，由 Leo 和 William Moser 兩位兄弟檔數學家所提出，後來被稱為莫澤圖 (Moser spindle)。

格雷的突破

同樣的道理，要證明 4 色不夠用的方法就是找一個至少需要 5 色的例子。

格雷受到莫澤圖的啟發，依照三四個步驟，一步一步建構出一個有著兩萬多個點的圖，這個圖無法只用 4 色完成著色。驗證這個反例可不容易，想像光是頂點數量超過兩萬的圖有多複雜，更別說要驗證 4 個顏色夠不夠用。此時，演算法就派上用場，寫個高效率的程式交給電腦處理就行了。

任何一個需要至少 5 色的圖都是這個問題的一項重大進展，數學家希望找到小一點且同樣需要 5 色的圖，最好當然是找到最小的那一種，如此一來就可以更深入地了解究竟需要 5 色的理由是什麼，怎樣的結構會造成顏色數增加，唯有透過不斷地分析解構，才可能更接近真相。

格雷也和華裔數學家陶哲軒等人的 polymath 團隊合作，希望藉由團隊的力量將點數大幅度下降。果然，不久後，俄亥俄州立大學的數學家 Dustin Mixon 和 Boris Alexeev 找到一個有 1577 個點的圖。沒多久，德州大學奧斯汀分校的資訊科學家 Marijn Heule 將點數縮小到 874，之後又進一步下降到 826。

不久後，由 Geoffrey Exoo and Dan Ismailescu 組成的團隊提出了另一個新的至少需要 5 色的證明。

一系列的改進給沉寂 60 年的 Hadwiger-Nelson 問題帶來一道曙光。不過，要決定正確答案究竟是多少，恐怕還得需要更多時間才有機會解開謎底，這時候，我心裡反倒暗暗希望格雷的一千歲理論是對的了。

這不是四色定理

這不是四色定理

這不是四色定理

有人可能會將這個「把平面上所有點著色的問題」跟那個「把平面圖的點著色問題」搞混。

雖然有點像在玩繞口令，但四色定理是關於後者，平面圖說的是可以把圖畫在平面上而又不使邊交叉；而前者將平面上無窮多點所形成的單位長度邊都畫好之後，並非平面圖。

參考資料

[1] Aubrey de Grey, The chromaticnumber of the plane is at least 5, arXiv:1804.02385v2

[2] Geoffrey Exoo and Dan Ismailescu, The chromatic number of the plane is at least 5 - a new proof, arXiv:1805.00157