張貼日期：Feb 22, 2020 11:3:49 AM

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

當然，顯而易見，如果小明沒有把錢拿去消費，民眾也找不到其他管道買口罩的情況下，答案就是 20元x3=60 元以及3隻x2=6 隻口罩，乘法用數學式子運算直接就能處理；更直觀一點，一項物品的「倍數」觀念基本上可以視為將該物品「複製貼上」那麼多次的總量。當然，物品是任何東西都能適用，即使是「圖」也不例外，這裡所謂的圖是指由點和邊(點與點的關係)所構成的一個抽象概念。一個圖乘以純數就是將該圖複製那麼多次，如下。

圖的乘法是什麼?

那麼問題來了，如果想要延伸乘法的概念到［圖乘以圖］又該如何定義。例如，

該等於什麼？

延伸定義的一種方法是讓［前圖］乘以 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）相連，請看下例。

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

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

赫德米猜想的考驗

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

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

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

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

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

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

[赫德米猜想 1966] 作張量積後的點著色數和原圖的點著色數較小的那個相同。

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

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

後來，艾狄胥-羅瓦胥的猜測被曾在台灣的中山大學現在浙江師範大學工作的朱緒鼎教授解決了。他在 2001 年提出一個當時看來相當大膽的問題，「赫德米猜想在分數著色數的形式對不對呢?」；約莫十年後，他回答了自己提的疑問，證明赫德米猜想的分數著色數(fractional chromatic number)版本是正確的。而他這項結果就足以證明艾狄胥-羅瓦胥猜測。分數著色是一種比傳統著色更細緻的形式，在此暫不贅述，要讀者知道的是即使在分數著色版本取得進展，原本的赫德米猜想仍是未知。不過，這卻提供了更進一步證據，讓人們有更多理由相信赫德米猜想是正確的。

希多夫的三頁論文

然而，一個反例就足以毀滅千千萬萬個美好假象。去年(2019 年)夏天，30歲的俄國年輕數學家亞羅斯拉夫·希多夫 (Yaroslav Shitov )提出一個反例狠狠地擊碎了赫德米猜想，震驚全世界圖論學家。

「我的博士論文主要研究題目之一就是赫德米猜想，數十年來一直深信它是正確的，沒想到竟然這麼美麗的猜想會錯了。」－朱老師在演講時這麼形容他內心的震撼。

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

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

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

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

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

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

你有發現螢幕髒髒的有根毛嗎? 不用擦了! 那根就是反例之毛。

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

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

[赫德米猜想的等價形式]

如果圖 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。根據上面的性質，這是不可能的事，除非赫德米猜錯了，因此得證。

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

希多夫之後的事

希多夫的結果證明赫德米猜錯了，張量積圖的著色數可以比原圖的著色數用的還要少，至少在原圖著色數很大很大的時候。ps. 數學家預測錯誤是常有的事，並不需要道歉哦。這點跟世界上許多的經濟學家和電視上的名嘴一樣，在預測股市錢途光明的美好未來或者發表令人恐慌的邪惡陰謀論，不幸發生錯誤時，也不曾有人為預測失準道歉，不一樣的是他們的預測往往能為他們帶來收入，但數學家沒有。數學家沒有就是沒有。真傷感….XD

從希多夫證明赫德米錯了之後，有一群數學家正努力要證明，赫德米不只錯了，還錯得很離譜! 這種平常視為落井下石的行為，在數學上是錦上添花。

如果兩個原圖都是著色數 n 的圖，令 f(n) 就是所有這種圖中產生的最小[張量積圖的著色數]。那麼赫德米猜想指的是，在任何情況下 f(n) 都等於 n；而希多夫的結果揭示當 n 很大的時候 f(n) 不需要到 n ，但沒說能夠少用多少個顏色!

至今甚至沒有人知道 f(n) 究竟是不是有界的 (會不會一直跟著 n 變大)。

有趣的是，雖然尚不能知道是不是有界，Poljak 和 Rödl 證明如果有界的話，那 f(n) 最多就是 16。蝦密?! 從有沒有界變成常數 16，也差太大了! 這個結論就像是在說「我不知道這個黑洞有沒有盡頭，不過我知道，如果有盡頭，那這黑洞最深就是 16 公尺」之類的。後來，朱老師的博士論文甚至下修這個量到 9。

去年底，沿著希多夫的建構思路，朱老師和 Claude Tardif 在網路上率先公開了一項結果:

定理[Tardif and Zhu 2019]: 當 n 很大時， f(n) 最多就是 n – (log n)^1/4 。

(也就是存在兩個著色數很大的圖，其張量積圖的著色數可以比它們少用 (log n)^1/4 多顏色。)

他們下降了使用的顏色數，隨即，另一組研究團隊 X. He 和 Y. Wigderson 又進一步下修到最多使用 (1-ε)n 個顏色，沒多久，朱老師又丟出一篇論文指出存在兩個著色數 n 很大的圖，其張量積圖卻只需要差不多一半那麼多顏色 n/2+o(1) 就夠了。這一切的變化發生在短短幾個月之內，結論就是［希多夫證明赫德米錯了，朱緒鼎證明赫德米錯得很離譜。］

圖為 2020.01.24 朱緒鼎老師@中研院數學所演講

參考資料

1. Y. Shitov, Counterexamples to Hedetniemi’s Conjecture, arXiv: 1905.02167v1, 2019.

2. Erica Klarreich (Quanta magazine), A 53-Year-Old Network Coloring Conjecture Is Disproved.

3. 朱緒鼎, Hedetniemi's Conjecture and Poljak-Rödl function. (2020.01.24在中研院的演講)

4. X. Zhu, On Hedetniemi's conjecture and the Poljak-Rödl function, arXiv:1911.12015, 2019