第六百零七章 柯克曼女生問題（圖論）(第1/2頁)

1850年，英格蘭國教會神父柯克曼在閒暇時間提出一個數學問題：“學校有15名女生，每天3人一組出去散步。要保證每週的7天內，任何兩人都有一次同組的經歷，但也只能有一次同組經歷。請問如何辦到？”，這就是柯克曼女生問題。

在現代數學家看來，這類問題最好的辦法把他們看成超圖——一堆三個節點或更多的節點組成的集合。15個女生就是節點，三人同組就看成這三個節點用三條線段(圖論術語會說三條邊)連線成的三角形。

柯克曼女生問題實際上就是問，有沒有一種三角形的排列，把這些女生節點連線起來，並且，這些三角形還不能共邊。共邊意味著兩個女生被同組安排了兩次。題設要求的安排意味著女生們每週都能相聚一次，而每一天都是和新朋友一起散步。

柯克曼提出這個問題之後，近200年來，無數相關問題吸引和困擾著數學家。

1973年，傳奇數學家埃爾德什提出了一個類似的問題。

他問能不能構造一個超圖，這個超圖擁有如下兩個看似矛盾的性質。

性質一，任意兩個節點都恰好被一個三角形包含，就和之前的女生一樣。性質一要求了三角形要非常的密。

性質二要求三角形要以某種精確的方式鋪得足夠廣(具體的說，就是任意拿出幾個三角形，三角形佔用的結點數要比三角形本身的數量至少多出三個)。

”這有點矛盾，這些物體的佈局你既要求區域性上稀疏，又要求整體上稠密。“加州理工學院的數學家康隆(david conlon)如是說道。

2022年 1 月，四位數學家透過一份長達 50 的論文，證明了只要節點足夠多，總是可以構造這樣的超圖。伯明翰大學的數學家羅(Allan Lo)說：“為了得到這個結果，他們用的辦法的技術性程度令人驚歎。”康隆也說：“這是一個非常優秀的成果。”

研究團隊建立了一個滿足埃爾德什苛刻要求的系統方法，該系統方法從一個隨機選擇的三角形的開始，極其小心地設計以後續過程以滿足他們的要求。“證明裡那些複雜困難的分支情況的數量是非常驚人的。”康隆說。

他們的證明策略是從一個三角形開始，細緻的構造這個超圖。舉個例子，你可以試想一下我們提到的15個女生，然後兩兩相連做線段。

我們需要從這些線段上描出我們需要的、滿足條件的一堆三角形：

第一，任意兩個三角形不共邊。(滿足這樣條件的系統叫做施泰納三元系)

第二，讓每個三角形的子集佔用足夠多的節點。

數學家們對此有個通俗的類比。

現在假設我們不是在描三角形，而是在用樂高積木建造房屋。

你建造的前幾個房子非常宏偉、堅固和精緻。

你建好這些後，就把它們放在旁邊備用。數學家把它們稱為”吸收器“。

現在，用剩下的樂高積木繼續隨意的建造房屋。

當剩下的樂高積木越來越少的時候，你會發現一些散落的積木，和一些搭建不完善的房屋。

這個時候，你可以從吸收器上抽出幾個積木塊，用在不完善的建築上。

因為吸收器非常的堅固，抽出一些積木不會導致嚴重的後果。

施泰納三元系中，你的構造的房屋就是吸收器。

吸收器在這裡就是精心挑選的線段(邊)。

如果發現無法把剩餘的三元組搭建成滿足條件的三角形時，可以使用吸收器中的線段進行調整。當你做完這些調整後，吸收器本身也融入到了各個三角形之中。

吸收器的辦法有時會遇到阻礙。

但是數學家們修補