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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

　　你建造的前幾個(gè)房子非常宏偉、堅(jiān)固和精致。

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

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

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

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

　　因?yàn)槲掌鞣浅５膱?jiān)固，抽出一些積木不會(huì)導(dǎo)致嚴(yán)重的后果。

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

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

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

　　吸收器的辦法有時(shí)會(huì)遇到阻礙。

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

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

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

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

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

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

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

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

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