首页房产资讯正文

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

夜上海论坛房产资讯 2024-08-05 07:21:52

文：陳宏賓（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 ）提出一個反例，狠狠地擊碎了赫德米猜想，震驚全世界圖論學家。朱緒鼎老師在演講時這麼形容他內心的震撼：

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

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

比全宇宙原子數量還要大的反例圖的一根毛

希多夫提出的「反例圖」非常巨大，可說大到一個不能想像的地步，他先是建一個約2²⁰⁰個點的圖G，再取圖G的指數圖（exponential graph）作為反例，依此建構方式得到的圖至少有「2²⁰⁰再取2²⁰⁰」那麼多點。

這個數量有多大？比全宇宙的原子數量還要多很多很多。

你說，這麼大的圖是要怎麼驗證，用電腦可以嗎？別傻了，孩子。就算把時下最夯的量子、AI等等展現人類最頂尖智力的東西全都摻在一起，揉成撒尿牛丸電腦也不行啦。神奇的是，人腦可以裝下這個圖，用數學可以驗證這個圖。

更有趣的是作者僅僅使用這圖的一咪咪（大約4¹⁰⁰⁰⁰個點的子圖）作為反例的解釋。打個比方，大概就像下圖這種感覺，整個反例圖超級超級大，僅僅用一根毛就說明這個圖是反例了。（但那根毛比全宇宙的原子數量還多就是了）

專業的讀者可能會好奇，赫德米猜想不是「關於兩個圖做張量積的著色問題」嗎？怎麼反例只剩一個圖，是不是哪裡怪怪的？

很好，有發現的人很棒，沒發現也沒關係。這是因為我跳了好幾步沒講，猜想有不同的表現形式，現在稍微把這些關聯補齊。

赫德米猜想的等價形式：
如果圖G和圖H的點著色數都大於常數c，則它們的張量積圖G x H的點著色數也會大於c。

接下來就是指數圖發揮效用的地方，指數圖跟張量積有一個已知的性質如下。

指數圖與張量積性質：
對於任意圖G，對於任意常數c>0，對圖G和常數c做指數圖H_G,c，則張量積圖G x H_G,c的點著色數必不大於c。

希多夫的論文就是指出：有一個圖G，也有一個常數c>0，且圖G的著色數大於 c，然後證明了這個G和c造成的指數圖的點著色數竟然大於c。根據上面的性質，這是不可能的事，除非赫德米猜錯了，因此得證。

希多夫震撼世人的3頁論文據了解已經被接受，將會發表在最頂尖的國際期刊《數學年鑑》（Annals of Mathematics），從審查到接受只花了不到兩個禮拜。赫德米猜想的正反之爭或許在此告一段落。這並不意味故事到達終點，如你所見，這個反例圖大的不得了，因此，許多研究正在想辦法找出更小的反例，任何更小反例的出現，都能讓圖的張量積點著色問題獲得進展。數學家想理解作張量積會讓著色數下降的關鍵核心究竟是什麼，從這個角度來說，或許故事才剛要開始呢。

參考資料

Y. Shitov, Counterexamples to Hedetniemi’s Conjecture, arXiv: 1905.02167v1, 2019.
Erica Klarreich（Quanta magazine）, A 53-Year-Old Network Coloring Conjecture Is Disproved.
朱緒鼎, Hedetniemi's Conjecture and Poljak-Rödl function.（2020.01.24在中研院的演講）
X. Zhu, On Hedetniemi's conjecture and the Poljak-Rödl function, arXiv:1911.12015, 2019

本文經UniMath授權轉載，原文刊載於此

夜上海论坛