懸宕50幾年的「赫德米猜想」，被一位年輕數學家用三頁論文擊碎

我們想讓你知道的是

懸宕50幾年的「赫德米猜想」是圖論領域主要猜想之一，許多學者對它的正確性深信不疑。然而去（2019）年中，俄國年輕數學家希多夫（僅30歲）提出一項令人跌破眼鏡的結果，證明赫德米猜想錯了。

文：陳宏賓（UniMath創辦人、中興大學應用數學系助理教授）

最近數學家在許多重要議題上面取得研究進展，其中一項是關於懸宕50幾年的「赫德米猜想」（Hedetniemi's conjecture），是圖論領域主要猜想之一，許多學者對它的正確性深信不疑。然而，去（2019）年中，俄國年輕數學家希多夫（僅30歲）提出一項令人跌破眼鏡的結果，證明赫德米猜想錯了。

「各位同學，翻開課本第56頁，今天老師要來教大家乘法。」如果你的小學數學老師沒有時常請假的話，你應該會在課堂上學到像這樣的題目：「小明一天的零用錢有20元，請問三天後小明有多少零用錢？」又或者，「民眾在七天可以買三片口罩，請問14天最多可以買到幾片口罩？」

當然，顯而易見，如果小明沒有把錢拿去消費，民眾也找不到其他管道買口罩的情況下，答案就是20元x3=60元，以及3片x2=6片口罩。

乘法用數學式子運算直接就能處理，更直觀一點，一項物品的「倍數」觀念，基本上可以視為將該物品「複製貼上」那麼多次的總量。當然，物品是任何東西都能適用，即使是「圖」也不例外，這裡所謂的圖是指由點和邊（點與點的關係）所構成的一個抽象概念。

一個圖乘以普通數字就是將該圖複製那麼多次，如下：

圖的乘法是什麼？

那麼問題來了，如果想要延伸乘法的概念到「圖乘以圖」又該如何定義。例如以下該等於什麼？

延伸定義的一種方法是讓「前圖」乘以3倍（就是貼3次），然後這3塊相對應的地方都要呈現「後圖」的關聯狀態。這種常見的圖乘法是相對直觀的方式，稱為笛卡爾乘積（Cartesian product）。

由於邊與邊相乘的結果形同一個方形，因此圖G和圖H的笛卡爾乘積，一般記為Ｇ□Ｈ。下圖是較複雜的例子：

今天的重點是另一種定義方法，稱為張量積（tensor product）。它的運算方式形如交叉，因此記為ＧｘＨ，如下圖中兩點｛a,b｝x兩點｛c,d｝會產生4個點（a,c）（a,d）（b,c）（b,d），每個點對應到原本圖G和圖H中各1個點形成的點對，兩點是否相連的準則仰賴其對應點是否在原圖中都相連。意即如果a和b相連，且c和d相連，則（a,c）和（b,d）相連。請看下例：

下面這圖更複雜一點，不過簡言之，相連的條件就是「在原本兩圖中同時都相連」。

各位觀眾，我說了這麼多，你覺得乘法是不是很有趣呢？

赫德米猜想的考驗

接下來，我們要進入圖的傳統點著色問題。一個傳統的點著色要求將圖中的每一頂點著色，同時使得相連的點必須著不同顏色。最少需要多少種顏色才能夠達成目標？這個數量稱為圖的「點著色數」（chromatic number）。

笛卡爾乘積形成的圖，由於包含了原來兩圖的結構，很明顯，笛卡爾積圖的點著色數「至少需要」兩圖中點著色數較大的那個量。1957年Gert Sabidussi證明這個量也就足夠了，把「至少需要」換成「恰好」，完整的刻劃笛卡爾積運算的點著色性質。

另一方面，張量積形成的圖用其中任一個原圖的點著色數就足夠將整個圖塗好色：參考原圖的著色法，每一層依照都塗相同的顏色即可，由於「相連的條件就是在原本兩圖中同時都相連。」，因此參考原圖的著色法就避開了同色的困擾。當然，根據上面的推理我們知道應參考著色數較小的那個圖來做比較有利。

coloring_(1) — 張量積所形成的新圖著色完全參考左圖，是個合法的著色。當然，換成參考上圖也可以。

至此，一個很自然的問題是，能不能用更少顏色呢？

1966年史帝芬．赫德米（Stephen Hedetniemi）在博士論文中提出這項猜測，他認為不可能更少了，也就是說：

作張量積後的點著色數，和原圖的點著色數較小的那個相同。

這個後來被稱為赫德米猜想（Hedetniemi's conjecture）的難題，是圖論領域的主要猜測之一。過去數十年來，許多研究圖論的學者也都曾嘗試解決這個問題，對於它的正確性，多年來有人持正面、也有人持反面態度。隨著時間過去，有許多證據浮現，然而卻一直未能有人能真正解決這個問題。

由一個剛畢業的博士所提出來的猜想，可想而知剛開始時並不會受到太多關注。赫德米猜想之所以成為學界的熱門題目，是搭了知名數學家艾狄胥（Paul Erdős）和羅瓦胥（László Lovász）的便車，兩位大師在合作的一篇論文中指出，赫德米猜想如果正確的話，能夠用來破解他們論文中的另一道難題，一項關於拉姆西著色數（chromatic Ramsey number）的猜測。因為這個緣故，赫德米猜想一夕成為學者競相追逐的聖盃。

後來，艾狄胥－羅瓦胥的猜測，被曾在台灣的中山大學、現在在浙江師範大學工作的朱緒鼎教授解決了。他在2001年提出一個當時看來相當大膽的問題：

赫德米猜想在分數著色數的形式對不對呢？

約莫10年後，他回答了自己提的疑問，證明赫德米猜想的分數著色數（fractional chromatic number）版本是正確的，而他這項結果就足以證明艾狄胥－羅瓦胥猜測。分數著色是一種比傳統著色更細緻的形式，在此暫不贅述，要讀者知道的是即使在分數著色版本取得進展，原本的赫德米猜想仍是未知。不過，這卻提供了更進一步證據，讓人們有更多理由相信赫德米猜想是正確的。

希多夫的三頁論文

然而，一個反例就足以毀滅千千萬萬個美好假象。去（2019）年夏天，30歲的俄國年輕數學家亞羅斯拉夫．希多夫（Yaroslav Shitov ）提出一個反例，狠狠地擊碎了赫德米猜想，震驚全世界圖論學家。朱緒鼎老師在演講時這麼形容他內心的震撼：

我的博士論文主要研究題目之一就是赫德米猜想，數十年來一直深信它是正確的，沒想到竟然這麼美麗的猜想會錯了。

希多夫的論文出乎意料的「短」，包含首頁摘要和末頁參考文獻僅僅只用了三頁！簡短但卻非常難以理解，我當時斷斷續續花了兩個禮拜才搞懂。你可能會認為，把反例的圖給出來，驗證一下不符合猜想的結論就搞定了，兩頁證明差不多是這樣吧。我下載論文當時跟你想的一樣，不過事實並非如此。