Nagyon nagy kis ugrás a gráfelméletben

Március 15-én érdekes szemináriumi bejelentések dübörögtek a kombinatorika, a számolás matematikai tanulmányozása területén. Három munkatárs azt tervezte, hogy másnap koordinált megbeszéléseket tartanak. Julian Sahasrabudhe matematikusokhoz szólna az angliai Cambridge-ben, miközben Simon Griffiths megosztaná a hírt Rio de Janeiróban és Marcelo Campos São Paulóban. Mindhárom előadásnak azonos címei és rejtélyes, kétmondatos absztraktjai „Erdős egy régi problémájával kapcsolatos közelmúltbeli előrelépésekre” utaltak. Miközben Erdős Pál, az 1996-ban elhunyt magyar matematikus pózolt több száz probléma pályafutása során a kombinatorikusok gyorsan kitalálták azt a konkrét kérdést, amelyről a trió beszélni tervezett. Pletykák kavarogtak a Ramsey-számnak nevezett dologról, amely az egyik legnehezebben kiszámítható mennyiség az egész matematikában.

A Ramsey-számok egy egész tudományágat szültek, az úgynevezett Ramsey-elméletet, amely a rendszerek hatalmas skálájában keresi az elkerülhetetlen mintákat.

Tegyük fel például, hogy megpróbálja elosztani az összes egész számot több gyűjtőhely között, és szeretné elkerülni, hogy egyenletesen elhelyezkedő számsorozatokat helyezzen el bármelyik gyűjtőzónában. A Ramsey-elmélet azt mutatja, hogy kudarcot vallasz (hacsak nincs végtelen sok vödröd). Az elmélet a legtöbbre alkalmazható, amit meg lehet számolni. Ennek központi tanulsága az, hogy „nem lehet teljesen kaotikus rendszert létrehozni” – mondta Benny Sudakov, a zürichi Svájci Szövetségi Technológiai Intézet matematikusa.

A Ramsey-szám számszerűsíti, hogy milyen nagynak kell lennie egy paradigmatikus példának ahhoz, hogy bizonyos minták elkerülhetetlenül megjelenjenek. De központi szerepe ellenére senki sem tudta kiszámítani a Ramsey-számot, kivéve a legegyszerűbb esetei. A legjobb, amit tehettek, hogy korlátokat (vagy korlátokat) találtak annak, hogy mi lehet. Az Erdős és egy munkatársa által közel egy évszázaddal ezelőtt megállapított felső határ már ekkor is alig mozdult.

Aztán a március 15-i szemináriumokon és egy később este közzétett cikkben a kutatók bejelentették, hogy exponenciálisan javították a Ramsey-szám felső korlátját.

– Elmerültem – mondta Yuval Wigderson, a Tel Avivi Egyetem matematikusa, amikor meghallotta az új eredményt. "Szó szerint remegtem fél órától egy óráig."

A pártvonalak

A Ramsey-elmélet leggyakrabban egész számokkal vagy gráfokkal kapcsolatban tesz fel kérdéseket. A gráf ebben az összefüggésben a csomópontoknak nevezett pontok gyűjteményeire utal, amelyeket éleknek nevezett vonalak kötnek össze, és amelyeknek olyan tulajdonságaik lehetnek, mint a hosszúság vagy – mint a Ramsey-számok esetében – a szín.

A teljes gráf bonyolult és egyszerű is – minden csomópont minden másik csomóponthoz kapcsolódik. A Ramsey-szám azt írja le, hogy egy teljes gráfnak hány csomópontot kell tartalmaznia ahhoz, hogy egy adott struktúrával rendelkezzen. Tegyük fel, hogy egy teljes gráf élei két szín egyikéhez vannak hozzárendelve: piros vagy kék. Tegyük fel, hogy megpróbálja úgy színezni az éleket, hogy elkerülje a csomópontok egy csoportjának azonos színű élekkel való összekapcsolását. 1930-ban Frank Ramsey bebizonyította, hogy ha egy gráf elég nagy, lehetetlenné válik, hogy elkerüljük a matematikusok által monokromatikus klikknek nevezett csomópontok csoportját, amelyek közös élei vagy teljesen pirosak vagy kékek.

Pontosan mekkora legyen egy gráf, mielőtt egy monokromatikus klikk kénytelen megjelenni? A válasz a klikk méretétől függ. Ramsey megmutatta, hogy létezik egy szám, amelyet most Ramsey-számnak hívnak, és amely a csomópontok minimális számát jelenti, amelyekhez adott méretű monokromatikus klikknek léteznie kell, függetlenül attól, hogy az élek milyen színűek.

De a Ramsey-szám méretét nehéz meghatározni. 1935-ben, öt évvel azután, hogy Ramsey kimutatta, hogy létezik, Erdős és Szekeres György új, szigorúbb felső korlátot adott arra vonatkozóan, hogy mekkora a Ramsey-szám egy adott méretű klikkre. De azóta a matematikusok alig tudtak javítani Erdős és Szekeres számításán.

Annak érdekében, hogy jobban megértse, mit jelent ez, tekintsünk egy klasszikus példát, amelyben a csomópontok a vendégeket képviselik egy partin. Színezd ki a két vendég közötti szegélyt pirosra, ha már találkoztak, és kékre, ha még nem. Bármilyen klikkméretet kiválaszthat – hívjon meg elegendő embert a buliba, és nem kerülheti el, hogy meghívjon egy olyan embercsoportot, akik mind ismerik egymást (a szó több értelmében vett klikk), vagy olyan emberek csoportját, akik még soha nem találkoztak.

"A legegyszerűbb dolog, amit egy grafikonon tartalmazhat, egy monokromatikus klikk" - mondta Mária Csudnovszkij, matematikus a Princeton Egyetemen. „Elképesztő, hogy minden hatalmas grafikonon találsz egyet ezek közül. Teljesen nem egyértelmű."

Az első néhány Ramsey-szám kiszámítása viszonylag egyszerű. Tegyük fel, hogy meg akarja tudni annak a legkisebb gráfnak a méretét, amelynél elkerülhetetlenül egy kettes méretű klikket kell tartani, vagy a matematikusok szerint R(2). Mivel egy teljes gráf két csomóponttal csak két csomópont, amelyeket egy él köt össze, és ennek az élnek vagy pirosnak vagy kéknek kell lennie, R(2) 2. Általánosabban, R(k), vagy a Ramsey-szám k, a csomópontok minimális száma, amelyen túl a gráf nem kerülheti el, hogy egy méretű klikket tartalmazzon k.

Nem olyan nehéz megmutatni, hogy egy 3-as méretű klikk Ramsey-száma vagy R(3) 6 (lásd az ábrát). De csak 1955-ben rögzítették az R(4)-et 18-ra. Az R(5) továbbra is ismeretlen – legalább 43, és nem nagyobb 48-nál. Bár ezek a számok kicsik, az összes lehetséges színezést nem lehet átszűrni. David Conlon, a California Institute of Technology munkatársa. Tekintsük a színezések számát egy 43 csomópontot tartalmazó teljes grafikonon. „903 éled van; ezek mindegyike kétféleképpen színezhető” – magyarázta. "Tehát kapsz 2-t⁹⁰³, ami csak csillagászatilag nagy.”

A klikk méretének növekedésével a Ramsey-szám leszögezése egyre nehezebbé válik. Erdős azt suttogta, hogy a matematikailag igényes idegenekkel való totális háború könnyebb lenne, mint kitalálni R(6), ami valahol 102 és 165 között van. A bizonytalanság tartománya gyorsan nő: Szerint Stanisław Radziszowski által összeállított becslések, R(10) olyan kicsi lehet, mint 798 és akár 23,556 10 is. De a matematikusok céljai messze túlmutatnak a XNUMX-es Ramsey-számon. Olyan képletet akarnak, amely jó becslést ad az R(k), akkor is – vagy különösen – amikor k rendkívül nagy.

„Nem ismerek olyan embert a kombinatorikában, aki legalább egy kicsit ne gondolkodott volna ezen a problémán” – mondta Wigderson. – Szerintem ez a probléma nagyon különleges.

A Bíróság végzése

Frank Ramsey eklektikus, briliáns figura volt, aki 26 évesen halt meg. Csak hetekkel a halála előtt, a Proceedings of the London Mathematical Society közzétett a papír amelyben Ramsey-számokat mutatott be. Ez a munka nem is grafikonokról szólt, hanem egy matematikai logikai problémáról. Ramsey bebizonyította, hogy egy bizonyos feltételeket kielégítő állításnak legalább egy részében igaznak kell lennie. Az egyik ilyen feltétel az volt, hogy a forgatókönyvek nagy „univerzuma” legyen az állítás tesztelésére. Ennek az eredménynek a lépcsőfokaként Ramsey megmutatta, hogy a Ramsey-szám véges.

Öt évvel később Erdős és Szekeres kimutatta, hogy a Ramsey-szám k kevesebb, mint 4^k. És 12 évvel azután Erdős megmutatta hogy nagyobb, mint körülbelül $latex sqrt{2}^k$. Ehhez kiszámolta annak az esélyét, hogy egy véletlenszerűen színezett élű gráf monokromatikus klikket tartalmaz. Ez a „valószínűségi” technika hatalmas befolyást gyakorolt ​​a gráfelméletre. Ez is csapdába esett R(k) két exponenciálisan növekvő kapufa között: $latex sqrt{2}^k$ és $latex 4^k$.

Ahogy teltek az évtizedek, számos matematikus megpróbálta csökkenteni a rést a Ramsey-szám lehetséges értékei között. Néhányuknak sikerült: 1975-ben Joel Spencer megduplázta az alsó határt. És egy sor papírt Conlon, Andrew Thomason és a Ashwin Sah lenyomta a felső határt körülbelül $latex 4^{log(k)^2}$ tényezővel 2020-ra. De a Ramsey-szám határainak méretéhez képest ezek a korrekciók kicsik voltak. Ezzel szemben Erdős és Szekeres képletében az R(k) < 4^k exponenciális javulás lenne, ami gyorsan növekedne k nagyobb lesz.

„Csak aranyos kis kérdésnek tűnik” – mondta Rob Morris, az IMPA, a brazil Tiszta és Alkalmazott Matematika Intézet matematikusa Rio de Janeiróban, aki Campossal, Griffithsszel és Sahasrabudhéval közösen írta az új eredményt. „Kicsit finom dolog értékelni. De az embereket ez nagyon érdekli.” Ez valószínűleg alábecsülés. „Ha 1936-ban bebizonyították volna, az emberek azt mondták volna: oké, akkor mi a nagy baj?” – mondta Bollobás Béla, aki Morris és Sahasrabudhe doktori tanácsadója volt a Memphisi Egyetemen. "Azóta bebizonyosodott, hogy ez egy nagyon nagy probléma, mert az évek során több ezer dolgozat született a Ramsey-probléma különféle változatairól." Mint Liana Yepremyan, az Emory Egyetem matematikusa azt mondta: "A Ramsey-számok hidat teremtenek a kombinatorika, valamint a valószínűség és a geometria között."

Játékelmélet

 2018 augusztusában Sahasrabudhe posztdoktori ösztöndíjas volt Morris mellett az IMPA-n. Ők ketten abban reménykedtek, hogy új projektbe kezdhetnek Griffithsszel, aki a közeli Pápai Katolikus Egyetemen tanít. Conlon papírja felkeltette a figyelmüket. A cikk felvázolta a Ramsey-szám exponenciális javításának lehetséges stratégiáját. Griffiths, Morris és Sahasrabudhe játszani kezdett az ötlettel.

„Az elején nagyon izgalmas volt” – emlékezett vissza Sahasrabudhe. Mint mondta, mindössze egy hónapba telt, hogy felvázolják érveiket.

Az volt a tervük, hogy az Erdős és Szekeres eredeti bizonyítékában használt gondolatokra építsenek, amelyek szerint $latex R(k) < 4^k$. Annak bizonyítására, hogy a Ramsey-szám legfeljebb  $latex 4^k$, képzeljen el egy játékot egy teljes grafikonon $latex 4^k$ csomópontokkal. A játéknak két játékosa van. Először is, az ellenfeled minden élt pirosra vagy kékre színez, abban a reményben, hogy a széleket oly módon színezi, hogy elkerülje a monokromatikus klikkek kialakulását. k csomópontokat.

Ha az ellenfeled végzett a színezéssel, a te dolgod egy monokromatikus klikk után kutatni. Ha találsz egyet, nyersz.

A játék megnyeréséhez egy egyszerű stratégiát követhet. Segít (metaforikusan) a csomópontok két vödörbe rendezésén gondolkodni. Az egyik vödör csomópontjai kék klikket, a másikban a csomópontok piros klikket alkotnak. Egyes csomópontok törlődnek, és soha többé nem hallanak róluk. Kezdetben mindkét vödör üres, és minden csomópont alkalmas arra, hogy bármelyikbe lépjen.

Kezdje bármelyik csomóponttal, amelyik tetszik. Ezután nézze meg az összekötő éleket. Ha az élek fele vagy több piros, törölje az összes kék élt és azokat a csomópontokat, amelyekhez kapcsolódnak. Ezután tegye az eredeti választást a „piros” vödörbe. Ennek a csomópontnak az összes piros éle még mindig él és virul, a vödör belsejéből tapadva a gráf többi részére. Ha az élek több mint fele kék, akkor hasonló módon törli a piros éleket és csomópontokat, és helyezze a kék vödörbe.

Ismételje addig, amíg már nem marad csomópont. (Mivel a grafikon elkészült, bármely ponton minden megmaradt csomópont mindkét gyűjtőhelyhez csatlakozik, amíg az egyikbe nem kerül.)

Ha végzett, nézzen bele a vödrökbe. Mivel egy csomópont csak azután került a piros vödörbe, hogy a kék szomszédait kiiktatták, a piros vödör összes csomópontja piros élekkel van összekötve – ezek egy vörös klikket alkotnak. Hasonlóképpen, a kék vödör kék klikket alkot. Ha az eredeti gráfnak legalább $latex 4^k$ csomópontja van, akkor bebizonyítható, hogy ezeknek a gyűjtőknek az egyiknek tartalmaznia kell legalább k csomópontok, garantálva a monokromatikus klikket az eredeti gráfban.

Ez az érvelés okos és elegáns, de két klikket hoz létre – egy kéket és egy pirosat –, pedig valójában csak egy kell. Hatékonyabb lenne mindig pirosra menni – magyarázta Conlon. Ennél a stratégiánál minden lépésnél ki kell választani egy csomópontot, törölni kell a kék széleit, és be kell dobni a piros vödörbe. A piros vödör gyorsan megtelik, és egy vörös klikket halmoztál fel k csomópontok feleannyi idő alatt.

De a stratégiádnak minden piros-kék színnél működnie kell, és nehéz eldönteni, hogy mindig találsz-e olyan csomópontot, ahol sok piros él. Így Conlon javaslatát követve fennáll annak a veszélye, hogy egy olyan csomópontba kerül, amelyhez szinte nincs piros él. Ez arra kényszerítené, hogy egyszerre törölje a grafikon egy hatalmas részét, aminek következtében a kattintás felépítésére kényszerülne, mielőtt kifogyna a csomópontokból. Conlon javaslatának végrehajtásához Griffithsnek, Morrisnak és Sahasrabudhének be kellett bizonyítaniuk, hogy ez a kockázat elkerülhető.

Nyílt könyves vizsga

A játékmenet frissítése során Griffiths, Morris és Sahasrabudhe egy kicsit körkörösebb utat követett. Ahelyett, hogy monokromatikus klikket építettek volna fel közvetlenül a csomópontok piros és kék vödrébe dobásával, először egy vörös könyvnek nevezett szerkezet felépítésére összpontosítottak.

A gráfelmélet szerint egy könyv két részből áll: van egy monokromatikus klikk, az úgynevezett „gerinc”, és egy másik, különálló csomópontcsoport, amelyet „oldalaknak” neveznek. A vörös könyvben a gerincen belüli csomópontokat összekötő összes él piros, csakúgy, mint a gerincet az oldalakkal összekötő élek. Az oldalakon belüli csomópontokat összekötő élek azonban tetszőleges színkombinációk lehetnek. Conlon 2018-as cikkében megjegyezte, hogy ha egy könyv lapjain belül vörös klikket találunk, akkor kombinálhatjuk a gerincvel, hogy nagyobb vörös klikket kapjunk. Ezzel két egyszerűbb keresésre bonthatja a nagy vörös klikk keresését. Először is keress egy piros könyvet. Aztán keress egy klikket a könyv lapjain.

Griffiths, Morris és Sahasrabudhe úgy akarta módosítani a játékot nyerő algoritmust, hogy az egy vörös könyvet építsen fel vörös klikk helyett. Bár csak hetekkel a projektjük után döntötték el ezt a tervet, évekbe telhet, mire sikerülni fog. Még mindig el kellett kerülniük az összes piros él elvesztésének veszélyét.

„Nagyon sokáig elakadtunk” – mondta Campos, aki 2021-ben csatlakozott a projekthez.

Idén januárban a négy matematikus megállapodott abban, hogy a probléma másik változatára váltanak. Ez a verzió bonyolultabbnak hangzik, de könnyebbnek bizonyult.

A csapat mindvégig a Ramsey R számra összpontosított (k), más néven „átlós” Ramsey-szám. Egy R(k) tartalmaznia kell k csomópontok, mindegyiket azonos színű élek kötik össze, de nem számít, hogy ez a szín piros vagy kék. Másrészt az „átlón kívüli” Ramsey-szám R(k, l) azt méri, mekkora legyen egy grafikon, mielőtt egy vörös kattintást tartalmazna k csomópontokat, vagy egy kék klikket l csomópontok. Ahelyett, hogy folytatták volna az átlós probléma megoldását, a csoport úgy döntött, hogy kipróbálja az átlón kívüli változatot. Ez kinyilatkoztatónak bizonyult.

„Sokáig úgy érezte, hogy minden ajtó, amelyet betoltak, be van reteszelve, vagy legalábbis elég nehéz bejutni” – mondta Griffiths. „És a változás után úgy érezted, minden ajtó nyitva van. Valahogy úgy tűnt, minden működik.” Az átlón kívüli változatban megtalálták a módját, hogy egy csomó kék élt egyszerre töröljenek egy adott protokollt követve, ami növelte a piros élek sűrűségét, és az átlón kívüli Ramsey-szám jobb korlátjához vezetett. Ezt a „sűrűségnövekmény” argumentumnak nevezett módszert korábban használták a megoldásra a kombinatorika egyéb fontos problémái, de nem használták a Ramsey-számproblémára.

A négy matematikus ezután az átlón kívüli Ramsey-szám új korlátját használta, hogy megszabadítsa az utat az átlós eredmény előtt. Február elejére végre egy exponenciális tényezővel csökkentették a Ramsey-szám határát, amire a matematikusok közel egy évszázada vágytak. És ezt úgy tették, hogy modernizálták ugyanazt az érvelést, amelyet Erdős és Szekeres 1935-ben felhozott.

Epszilon, Epszilon

A március 16-i megbeszélések után a résztvevők elkezdték megerősíteni a pletykákat. A Sahasrabudhe beszélgetéséről készült fotók telefonhívásokon és privát üzeneteken keresztül terjedtek – még a homályos, de sokat sejtető bejegyzés Gil Kalai matematikus blogján. Campos, Griffiths, Sahasrabudhe és Morris azt állították, hogy kimutatták, hogy $latex R(k) < 3.993^k$. Aznap este a négy szerző közzétették lapjukat az interneten, lehetővé téve a matematikusok számára, hogy maguk is lássák az új bizonyítékot.

„Azt hiszem, sokan nem számítottunk arra, hogy életük során ekkora javulást látunk” – mondta Matija Bucić, a Princeton Egyetem és az Institute for Advanced Study matematikusa. "Szerintem ez egy teljesen elképesztő eredmény."

Sok szakértő abban reménykedik, hogy az exponenciális akadály lebontásával hamarosan további előrelépések következnek be. Az új cikk szerzői szándékosan nem feszegették módszerüket a határokig, nehogy felesleges részletekkel homályosítsák el érvelésüket. "Nagyon érdekel, hogy meddig mehet el a módszer, mert fogalmam sincs" - mondta Campos.

„Ez egy teljesen zseniális, teljesen csodálatos bizonyíték, és valódi áttörés. Így most arra számítok, hogy kinyitják a zsilipeket” – mondta Bollobás. „Meggyőződésem, hogy három év múlva a vita a lehetséges fejlesztésekről fog szólni. Javíthatjuk a 3.993-at 3.9-re? Talán 3.4-re? És mi van a 3-mal?"

Az új bizonyíték 56 oldalas, és hetekbe telhet, amíg a kombinatorika közösség minden részletet teljesen ellenőriz. A kollégák azonban optimisták. „Ez a szerzőcsoport nagyon komoly emberek. És olyan emberek, akik nagyon-nagyon jók nagyon technikai dolgokban” – mondta Wigderson.

Amikor munkatársairól van szó, Griffiths egyetért. „Kiváltság zseniális emberekkel dolgozni, nem igaz? És azt hiszem, ezért nagyon hálás vagyok” – mondta. „Ha rám bíznák, még öt évbe telt volna, hogy rendbe tegyem a részleteket.”