第六百零七章 柯克曼女生問題（圖論）

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

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

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

　　柯克曼提出這個問題之后，近200年來，無數(shù)相關(guān)問題吸引和困擾著數(shù)學(xué)家。

　　1973年，傳奇數(shù)學(xué)家埃爾德什提出了一個類似的問題。

　　他問能不能構(gòu)造一個超圖，這個超圖擁有如下兩個看似矛盾的性質(zhì)。

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

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

　　”這有點矛盾，這些物體的布局你既要求局部上稀疏，又要求整體上稠密?！凹又堇砉W(xué)院的數(shù)學(xué)家康隆(David Conlon)如是說道。

　　2022年 1 月，四位數(shù)學(xué)家通過一份長達 50 的論文，證明了只要節(jié)點足夠多，總是可以構(gòu)造這樣的超圖。伯明翰大學(xué)的數(shù)學(xué)家羅(Allan Lo)說：“為了得到這個結(jié)果，他們用的辦法的技術(shù)性程度令人驚嘆?！笨德∫舱f：“這是一個非常優(yōu)秀的成果?！?p>　　研究團隊建立了一個滿足埃爾德什苛刻要求的系統(tǒng)方法，該系統(tǒng)方法從一個隨機選擇的三角形的開始，極其小心地設(shè)計以后續(xù)過程以滿足他們的要求?！白C明里那些復(fù)雜困難的分支情況的數(shù)量是非常驚人的?！笨德≌f。

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

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

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

　　第二，讓每個三角形的子集占用足夠多的節(jié)點。

　　數(shù)學(xué)家們對此有個通俗的類比。

　　現(xiàn)在假設(shè)我們不是在描三角形，而是在用樂高積木建造房屋。

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

　　你建好這些后，就把它們放在旁邊備用。數(shù)學(xué)家把它們稱為”吸收器“。

　　現(xiàn)在，用剩下的樂高積木繼續(xù)隨意的建造房屋。

　　當(dāng)剩下的樂高積木越來越少的時候，你會發(fā)現(xiàn)一些散落的積木，和一些搭建不完善的房屋。

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

　　因為吸收器非常的堅固，抽出一些積木不會導(dǎo)致嚴重的后果。

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

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

　　如果發(fā)現(xiàn)無法把剩余的三元組搭建成滿足條件的三角形時，可以使用吸收器中的線段進行調(diào)整。當(dāng)你做完這些調(diào)整后，吸收器本身也融入到了各個三角形之中。

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

　　但是數(shù)學(xué)家們修補了這個問題，他們找到了一種新辦法繞過這些阻礙。

　　比如，有一種叫做迭代吸收器的，它將線段劃分成嵌套集合序列，于是每個吸收器都是會為下一級迭代服務(wù)。

　　”十多年來，進步巨大，“康隆說?！边@已經(jīng)是某種藝術(shù)形式，如果看成藝術(shù)，他們展示了一個非常高級的藝術(shù)?！?p>　　即便有了迭代吸收器，埃爾德什問題也依舊很難。”這就是問題沒有得到解決的原因“，論文其中一個作者索尼(Mehtaab Sawhney)說。

　　比如，在迭代吸收的其他應(yīng)用中，一旦你完成了一個集合的構(gòu)建——無論是三角形、泰納三元系，還是其他結(jié)構(gòu)——你可以認為事情告一段落并扔在一邊。然而，埃爾德什的條件要求讓這四位數(shù)學(xué)家不能這樣做。有問題的三角形很容易觸及多個吸收器的節(jié)點。

　　“一個你在500 步前選擇的三角形，你需要以某種方式記住，并知道如何處理它，”索尼說。

　　這四個人最終發(fā)現(xiàn)，如果他們選擇的三角形足夠精細，他們就可以繞過每一個小問題?！白詈玫霓k法是考慮每個由 100 個三角形組成的子集，并保證以正確的可能性挑選三角形，”索尼說。

　　論文的作者們樂觀地認為，他們的這個方法可以推廣到別的問題。他們已經(jīng)將他們的方法應(yīng)用于一個關(guān)于拉丁方的問題——一個簡化版的數(shù)獨問題。

　　除此之外，還有幾個問題最終可能被吸收器方法解決。“組合學(xué)中，尤其是在組合設(shè)計論中，隨機過程是一個非常強大的工具?！逼渲幸粋€也是關(guān)于拉丁方的問題叫做Ryser-Brualdi-Stein 猜想，自 1960 年代以來一直沒有解決。

　　智利大學(xué)的數(shù)學(xué)建模中心的副主任斯坦恩(Maya Stein)說，雖然吸收器方法可能需要進一步發(fā)展才能解決這個問題，但自 30 年前方法建立以來，它已經(jīng)走過了漫長的道路?！翱吹竭@些方法是如何進步和豐富起來，真是人生一大幸事?！?