阿貝爾獎得主Lovász：我提出了四色猜想的進階版，它很簡單，50年后就被證明了......

阿貝爾獎得主Lov%uE1sz：我提出了四色猜想的進階版，它很簡單，50年后就被證明了......

繼四色猜想之后，超圖著色猜想也被數學家攻克了。這距離超圖著色猜想初次被提出已經過去近50年，距離四色猜想被證明，也已經過去了45年。

而證實這一猜想是來自英國伯明翰大學的五位數學家，他們分別是Daniela K%uFChn、Deryk Osthus、Tom Kelly、Abhishek Methuku以及Dong yeap Kang。其中前兩位為資深數學家，后三位為博士后。

在1月份提交的一份預印論文中，他們采用線性超圖的算法對三種極端超圖案例進行了實驗，在確保重疊邊緣不出現相同顏色的情況下，證明了著色的數目永遠不會大于超圖中頂點的數目。

論文鏈接：https://arxiv.org/pdf/2101.04698.pdf

1 進階版的四色猜想

四色定理又稱為四色地圖定理：如果在平面上劃出一些鄰接的有限區域，那么可以只用四種顏色來給這些區域染色，使得每兩個鄰接區域染的顏色都不一樣。

這個問題最早是由南非數學家法蘭西斯·古德里在1852年提出的，并與費馬大定理、哥德巴赫猜想并列世界三大數學猜想。

圖注：四色定理的一個案例。

人們發現，要證明寬松一點的“五色定理”（即“只用五種顏色就能為所有地圖染色”）很容易，但四色問題卻出人意料地異常困難。曾經有許多人發表四色問題的證明或反例，但都被證實是錯誤的。

1976年，數學家凱尼斯·阿佩爾和沃夫岡·哈肯借助電子計算機首次得到一個完全的證明，四色問題也終于成為四色定理。這是首個主要借助計算機證明的定理。四色定理的本質正是二維平面的固有屬性，即平面內不可出現交叉而沒有公共點的兩條直線。

四色問題還可以轉化為拓撲學版本，即更為抽象的圖論版本。

圖論是數學的一個分支，它以圖為研究對象。圖論中的圖是由若干給定的點及連接兩點的線所構成的圖形，這種圖形通常用來描述某些事物之間的某種特定關系，用點代表事物，用連接兩點的線表示相應兩個事物間具有這種關系。

這里的轉化指的是一種對偶的概念，即將一個地圖轉化為圖論中的一個無向平面圖。

圖注：將平面四色問題轉化為圖論四色問題。

具體來說，是將地圖中的每一個國家用其內部的一個點代表，作為一個頂點。如果兩個國家相鄰，就在兩個頂點之間連一條線。這樣得到的圖必然是一個平面圖（不會有兩條邊相交），而與每個國家選取的代表點無關。

圖論版本的四色定理可以敘述為：必然可以用四種顏色給平面圖的頂點染色，使得相連的頂點顏色不同。

而在圖論領域，還存在一種超出日常直覺（或者說歐幾里得直覺）的圖形——超圖，超圖中的邊可以連接多于兩個頂點。超圖也有著對應的“四色猜想”——超圖著色猜想，可以稱之為進階版的四色猜想。

50年前，保羅·埃爾德斯（Paul Erd%u151s）和另外兩位數學家提出了一個圖論（ Graph theory）問題。

Paul Erd%u151s

他們認為，要給線性超圖的邊著色所需要的的顏色數量將不會超過圖形的頂點數量。

值得一提的是，Erd%u151s曾提出過數以千計的問題，但這個著色猜想是他最喜歡的三個猜想之一。為鼓勵更多數學家來解決它，Erd%u151s還將懸賞金增加到了500美元，但近50年來，沒有一個人取得成功。

2 超圖著色猜想的誕生

1972年秋天，兩位頗具影響力的數學家保羅·埃爾德斯（Paul Erd%u151s）和拉斯洛·洛瓦茲（L%uE1szl%uF3 Lov%uE1sz）來訪，科羅拉多大學教授萬斯·費伯（ Vance Faber ）舉辦了一場學術交流會。

值得一提的是，L%uE1szl%uF3 Lov%uE1sz在國際上享有盛譽，上個月他剛剛與美國普林斯頓高等研究院教授艾維·維格森（Avi Wigderson）共同獲得了被譽為數學界“諾貝爾獎”的阿貝爾獎。此次表彰旨在獎勵他們“對理論計算機科學和離散數學的基礎性貢獻，以及在將它們推動至現代數學的中心領域方面的領導作用。”

據悉，該獎項與菲爾茲獎、沃爾夫數學獎并稱國際數學界“三大獎”。

在會上，Erd%u151s、Faber和Lov%uE1sz三位學者將談話的重點聚焦在了超圖（Hypergraphs）上，超圖是當時圖論學中一個很有趣的新概念。經一番辯論之后，他們提出了一個問題：在一定的約束條件下，為超圖的邊著色所需的最小顏色數。后來它被稱為Erd%u151s-Faber-Lov%uE1sz猜想。

Faber現在是國防分析研究所計算科學中心（ Defense Analyses’ Center for Computing Sciences）的數學家，他說，“當時我們認為這是會上最簡單的問題，第二天就可以解決，顯然我們低估了它”。事實證明，這個問題比預期的困難要大得多。

后來，Erd%u151s, Faber and Lov%uE1sz 三人提出了一種新的圖形結構——超圖。普通圖形由頂點和邊線連接而成，每條邊正好可以連接兩個頂點，相比之下，超圖沒有這方面的限制：它們的邊可以鏈接任意數量的頂點。

這種概念從直觀上可能比較難想象，但寬泛的邊概念使超圖比以同類圖更加通用。標準圖只能表示成對事物之間的關系，比如社交網絡中的兩個朋友（每個人都由一個頂點表示）。但是要表達兩個以上的人之間的關系，就像一個團隊中的共享成員一樣，每個邊需要包含兩個以上的人，這是超圖所能呈現的。超圖模型的基本設定就是一個邊可以包含大于 2 個點，去擬合多元關系。

圖注：超圖的圖示，其中每條邊可以連接超過兩個的頂點，上圖中三個方框里的超圖都只有三條邊。

然而，這種多功能性是有代價的：超圖比普通圖更難證明其普適性。

IDC Herzliya和耶路撒冷希伯來大學的Gil Kalai說：“當你轉向超圖時，（圖論的）許多奇跡要么消失，要么變得更加困難”。

例如在邊著色問題上。在為超圖上色過程中，若頂點處相交的兩條邊沒有相同顏色，這種情況下所需的最小顏色數被稱為圖的色指數。Erd%u151s-Faber-Lov%uE1sz猜想是關于一類邊重疊最小的超圖的著色問題。在這些被稱為線性超圖的結構中，兩條邊最多只能在一個頂點重疊。比如在一個線性超圖中，邊a連接頂點1、2、3，邊b連接2、3、4是不被允許的，但連接1、4、5是允許的。這個猜想預言：線性超圖的色指數永遠不會超過它的頂點數。

換句話說，如果一個線性超圖有九個頂點，不管如何繪制，它的邊都可以用不超過九種顏色著色。

此次論證的作者之一的Dong yeap Kang教授表示，為了證明這一猜想的普適性，他們挑戰了著色問題最極端三種超圖案例。

3 三種極端超圖案例

通常情況下，隨機繪制一個線性超圖，它的顏色指數可能都會遠遠小于頂點數，但在三種特殊超圖下會出現例外。

第一種超圖被稱為完全圖（ Complete Graph），它的每條邊只連接兩個頂點。由于每一對頂點都由一條邊連接，具有奇數個頂點的完全圖具有Erd%u151s-Faber-Lov%uE1sz猜想所允許的最大色指數。

第二種超圖在某種意義上，與完全圖相反。當一個完全圖中的邊只連接少量頂點（兩個）時，這類圖中的所有邊都連接大量頂點（隨著頂點總數的增加，每個邊所包含的數目也會增加），它被稱為有限射影平面，和完全圖一樣，它也有最大的色指數。

第三種超圖屬于過渡情況——小邊只連接兩個頂點，大邊連接多個頂點。在這種類型的圖中，通常有一個特殊的頂點通過單獨的邊連接到其他每個頂點，然后有一個大的邊將其他所有的頂點都連接起來。

如果調整三種特殊超圖中的一個，結果通常也會具有最大的色指數。因此，這三個例子中的每一個都代表了一個更廣泛的且具有挑戰性的超圖家族，這些超圖多年來阻礙了數學家證明Erd%u151s-Faber-Lov%uE1sz猜想的努力。

當數學家第一次遇到這個猜想時，他們可能會嘗試通過生成一個簡單的算法過程來證明——指定要分配給每個邊的顏色。需要強調的是，該算法需要適用于所有的超圖，并且只使用與頂點數量相同的顏色。

另外，三個特殊的超圖家族的形狀差異很大，因此，任何證明可能給其中一個家族著色的技術，在另外兩個族的超圖中都是失敗的。如Kang所說，“很難有一個共同的定理來包含所有的特殊情況。”

雖然Erd%u151s、Faber和Lov%uE1sz知道這三種極端超圖，但他們不知道是否還有其他的超圖具有最大的色指數。在這次最新論證中，來自伯明翰大學的5位數學家證明了包括這三種情況在內的所有超圖，它們所需的顏色數量都少于其頂點數。Abhishek Methuku說：“如果把這三種超圖家族排除在外，我們就可以證明沒有其他的特殊例子了。”

4 按序著色，小邊采用“吸收”法

需要說明的是，這個新證明是建立在羅格斯大學Jeff Kahn教授的研究基礎之上的。Jeff Kahn在1992年證明了Erd%u151s-Faber-Lov%uE1sz猜想的近似版本。

去年11月，伯明翰大學兩位資深數學家K%uFChn和Osthus，與Kang、Kelly和Methuku三位博士后組成團隊著手改進Kahn的結果，以試圖解決全部猜想。

Methuku表示，在剛開始工作時，他們就意識到也許能夠準確地證明這個猜想。他說，“非常幸運的是，不知何故，我們所擁有的團隊正好有解決這個問題的能力。”

該團隊結合許多技術創建了一個覆蓋所有類型的線性超圖的算法。首先，他們根據邊的大?。ㄓ蛇呥B接的頂點數決定）將給定超圖的邊分為不同的類別。

極品執事 http://www.cityruyi.com/lm-4/lm-3/706.html