1972年秋天，Vance Faber是科羅拉多大學的新教授。當兩位有影響力的數學家PaulErdős和LászlóLovász來訪時，Faber決定舉辦一場茶話會。尤其是Erdős，他是一位古怪而充滿活力的研究人員，在國際上享有盛譽，Faber的同事渴望與他見面。

Erdős，Faber和Lovász將他們的討論重點放在了超圖（hypergraph）上，這在當時的圖論中是一個很有前途的新想法。經過一番辯論，他們提出了一個問題，後來被稱為Erdős-Faber-Lovász猜想，即在某些限制下為超圖的邊緣著色所需的最小顏色數。

事實證明，這個問題比預期的要難得多。

Erdős經常將這個猜想和同行分享，併為解決方案提供了獎勵。數學家們逐漸意識到這個猜想的困難之處，獎勵也增加到了500美元，許多數學家嘗試後都失敗了。

將近50年之後，5位數學家在arxiv上釋出了一篇論文，他們對某些超圖的邊緣加陰影所需的顏色數量進行了限制，以使重疊的邊緣不會具有相同的顏色。他們證明顏色的數量永遠不會比超圖中的頂點數量大。

論文中提出的方法留出圖形的某些邊緣並隨機給其他邊緣著色，這是研究人員近年來為解決許多長期存在的開放性問題所運用的思想的組合。

Lovász認為這篇論文是一件美麗的作品。

什麼是超圖著色問題？

普通圖是由頂點構建的，這些點由邊連線。每個邊正好連線兩個頂點，而超圖的邊可以連線任意數量的頂點。

超圖的邊具有更廣泛的概念，標準圖只能表示事物對之間的關係，例如社交網路中的兩個朋友（每個人都由一個頂點表示）。但是，要表達多於兩個人之間的關係（例如組中的共享成員身份），每個邊都需要包含多於兩個人，這是超圖允許的。

但是，這種多功能性是有代價的：證明超圖的通用特性比普通圖更難，超圖模型使邊著色問題變得更加困難。

著色問題的目標是為圖（或超圖）的所有邊著色，以使在頂點處相交的兩個邊具有不同的顏色。為此所需的最少顏色數稱為圖形的色度指數（chromatic index）。

Erdős-Faber-Lovász猜想是關於特定型別的超圖的著色問題，其中邊重疊最少。在這些線性超圖的結構中，不允許兩個邊在一個以上的頂點處重疊。該猜想預測線性超圖的色度指數永遠不會超過其頂點數。換句話說，如果線性超圖具有九個頂點，則無論如何繪製，其邊緣都可以使用不超過九種顏色進行著色。

Erdős-Faber-Lovász猜想的極端普遍性使其難以證明。當超圖有更多頂點時，其迴圈邊的排布方式也會成倍增加。在所有這些可能性下，似乎有些邊需要比頂點多的顏色。

三種極端超圖

如果您在頁面上塗鴉並且繪製線性超圖，則其色度索引可能會遠遠小於其頂點數。但是，有三種類型的極限超圖推動了極限。

在第一個例子中，每個邊僅連線兩個頂點。通常將其稱為完整圖，因為每對頂點都是透過一條邊連線的。具有奇數個頂點的完整圖具有Erdős-Faber-Lovász猜想所允許的最大色度指數。

第二個例子和完整圖完全不同，此類圖中的所有邊都連線大量頂點，隨著總頂點數的增加，每個邊所包含的數目也隨之增加。它稱為有限投影平面，並且像完整的圖一樣，它具有最大的色度指數。

第三個例子在多種顏色的邊中間僅連線兩個頂點，而大邊緣則連線許多頂點。在這種型別的圖形中，通常會有一個特殊的頂點透過孤立的邊與每個其他的頂點相連，然後是一個單獨的長邊，將所有其他頂點都連線起。

如果稍微修改三個極端超圖之一，則結果通常也將具有最大的色度指數。這三個示例中的每一個都代表了一個更具挑戰性的超圖族。

要建立一個包含所有極端情況的共同定理是相當困難的。任何一個演算法解決了其中一種情況，通常來說對另外兩種情況都不會奏效。

雖然Erdős，Faber和Lovász知道這三個極端超圖，但他們不知道是否還有其他的最大色度指數。

新的證明建立在Jeff Kahn的進步基礎上，他在1992年證明了Erdős-Faber-Lovász猜想的近似版本。

去年11月，Kühn和Osthus以及他們的三個博士生Kang，Kelly和Methuku著手改善Kahn的工作。

他們首先根據邊連線的頂點數量將超圖的邊分為幾個不同的類別。

排序之後，他們首先轉向最難著色的邊：具有最多頂點的邊。

他們將這些邊重新配置為普通圖的頂點（每個邊僅連線兩個頂點）。他們使用標準圖論的既定結果對它們進行著色，然後將該顏色傳輸回原始的超圖。

迭代這個過程，直到最小邊也著色完畢。小邊接觸的頂點較少，更易於著色。當作者到達較小的邊緣時，許多可用的顏色已經在其他相鄰的邊緣上使用。

作者使用組合數學中的absorption作為逐漸到著色的方法，同時確保著色始終不衝突，這種技巧對於將特殊的頂點連線到第三個極限超圖中的所有其他頂點特別有用，這類超圖幾乎使用了所有可用的顏色。

absorption提高了隨機著色過程的效率，相比隨機著色可能產生的顏色浪費來說，absorption能夠減弱隨機著色的靈活性，這是一種更精確的方法。

最後，作者提出一個演算法為圖的最大邊著色，然後使用absorption和其他方法對較小的邊著色，作者能夠證明為任何線性超圖的邊緣著色所需的顏色數量絕不超過頂點數。這證明了Erdős-Faber-Lovász猜想是正確的。

由於機率因素，它們的證明僅適用於足夠大的超圖，即那些具有特定數量以上頂點的超圖。這種方法在組合數學中很常見，數學家認為它幾乎是完整的證明，因為它僅忽略了有限數量的超圖。

Lovász認為，從本質上講，他們已經證明了這一猜想。

為證明一個猜想而做出的努力迫使人們發現了更通用的技術，這也是從事數學的工作方式。

參考資料：

https：//www。quantamagazine。org/mathematicians-settle-erdos-coloring-conjecture-20210405/

https：//arxiv。org/pdf/2101。04698。pdf

TAG: 超圖頂點著色FaberLov