Zelo velik majhen korak naprej v teoriji grafov

15. marca so zanimive napovedi seminarjev povzročile hrup po polju kombinatorike, matematične študije štetja. Trije sodelavci so načrtovali usklajene pogovore naslednji dan. Julian Sahasrabudhe bi nagovoril matematike v Cambridgeu v Angliji, medtem ko Simon Griffiths bi novico delil v Riu de Janeiru in Marcelo Campos v São Paulu. Vsi trije govori so nosili enake naslove in skrivnostne, dvostavčne povzetke, ki se nanašajo na "nedavni napredek pri starem problemu Erdősa." Medtem ko je Paul Erdős, madžarski matematik, ki je umrl leta 1996, poziral na stotine težav v njegovi karieri so kombinatorci hitro razbrali konkretno problematiko, o kateri namerava trojica spregovoriti. Krožile so govorice o nečem, kar se imenuje Ramseyevo število, ki je ena izmed najtežje izračunanih količin v vsej matematiki.

Ramseyeva števila so ustvarila celotno disciplino, imenovano Ramseyeva teorija, ki išče neizogibne vzorce v velikem obsegu sistemov.

Recimo, da poskušate razporediti vsa cela števila med vedra in se želite izogniti umeščanju zaporedij enakomerno razporejenih števil v katero koli vedro. Ramseyjeva teorija kaže, da vam ne bo uspelo (razen če imate neskončno veliko veder). Teorijo je mogoče uporabiti za skoraj vse, kar lahko preštejete. Njegova osrednja lekcija je, da "ne morete ustvariti popolnoma kaotičnega sistema," je dejal Benny Sudakov, matematik na švicarskem zveznem inštitutu za tehnologijo v Zürichu.

Ramseyevo število kvantificira, kako velik mora biti paradigmatični primer, preden se neizogibno pojavijo določeni vzorci. Toda kljub osrednjemu pomenu nihče ni mogel izračunati Ramseyevega števila za vse, razen za najpreprostejši primeri. Najboljše, kar so lahko naredili, je, da so našli omejitve (ali meje) tega, kar bi lahko bilo. Tudi takrat se je zgornja meja, ki sta jo prvi postavil Erdős in njegov sodelavec pred skoraj stoletjem, komaj premaknila.

Nato so na seminarjih 15. marca in v prispevku, objavljenem pozneje istega večera, raziskovalci objavili, da so eksponentno izboljšali zgornjo mejo Ramseyevega števila.

"Bil sem na tleh," je rekel Yuval Wigderson, matematik na Univerzi v Tel Avivu, ko je slišal za nov rezultat. "Od pol ure do ene ure sem se dobesedno tresel."

Linije stranke

Ramseyeva teorija najpogosteje postavlja vprašanja o celih številih ali o grafih. Graf se v tem kontekstu nanaša na zbirke točk, imenovanih vozlišča, povezanih s črtami, imenovanimi robovi, ki imajo lahko lastnosti, kot je dolžina ali - kot v primeru Ramseyevih števil - barva.

Celoten graf je hkrati zapleten in preprost – vsako vozlišče je povezano z vsakim drugim vozliščem. Ramseyevo število opisuje, koliko vozlišč mora vsebovati celoten graf, da ima določeno strukturo. Recimo, da je robom celotnega grafa dodeljena ena od dveh barv: rdeča ali modra. In recimo, da poskušate obarvati robove tako, da se izognete povezovanju skupine vozlišč z robovi iste barve. Leta 1930 je Frank Ramsey dokazal, da če je graf dovolj velik, se je nemogoče izogniti ustvarjanju tega, čemur matematiki pravijo monokromatska klika - skupina vozlišč, katerih skupni robovi so bodisi vsi rdeči ali vsi modri.

Kako velik mora biti natančno graf, preden se pojavi monokromatska klika? Odgovor je odvisen od velikosti klike. Ramsey je pokazal, da obstaja število, ki se zdaj imenuje Ramseyevo število in predstavlja najmanjše število vozlišč, za katera mora obstajati enobarvna klika dane velikosti, ne glede na to, kako so robovi obarvani.

Toda velikost Ramseyevega števila je težko določiti. Leta 1935, pet let po tem, ko je Ramsey pokazal, da obstaja, sta Erdős in George Szekeres zagotovila novo, strožjo zgornjo mejo, kako veliko je Ramseyevo število za kliko določene velikosti. Toda od takrat matematiki komajda uspejo izboljšati Erdősov in Szekeresov izračun.

Če želite bolje razumeti, kaj to pomeni, razmislite o klasičnem primeru, v katerem vozlišča predstavljajo goste na zabavi. Obarvaj rob med dvema gostoma rdeče, če sta se že srečala, in modro, če se še nista. Izberete lahko poljubno velikost klike – na zabavo povabite dovolj ljudi in ne morete se izogniti povabilu skupine ljudi, ki se med seboj poznajo (klika v več pomenih besede) ali povabilu skupine ljudi, ki še nikoli prej nista srečala.

"Najenostavnejša stvar, ki jo lahko imate v grafu, je enobarvna klika," je rekel Marija Čudnovska, matematik na univerzi Princeton. »Nekako neverjetno je, da lahko v vsakem ogromnem grafu najdete enega velikega. Popolnoma ni jasno.”

Prvih nekaj Ramseyjevih števil je razmeroma enostavno izračunati. Recimo, da želite vedeti velikost najmanjšega grafa, ki mora neizogibno vsebovati klik velikosti dve ali R(2) za matematike. Ker sta celoten graf z dvema vozliščema le dve vozlišči, povezani z robom, ta rob pa mora biti rdeč ali moder, je R(2) 2. Bolj splošno je R(k), ali Ramseyevo število k, je najmanjše število vozlišč, nad katerim se graf ne more izogniti vsebovanju klike velikosti k.

Ni tako težko pokazati, da je Ramseyevo število za kliko velikosti 3 ali R(3) 6 (glej sliko). Toda šele leta 1955 je bil R(4) pripet na 18. R(5) ostaja neznan – je vsaj 43 in ne večji od 48. Čeprav so te številke majhne, ​​je presejanje vseh možnih barv izpadlo. na vprašanje, je dejal David Conlon s kalifornijskega tehnološkega inštituta. Upoštevajte število barv na celotnem grafu s 43 vozlišči. »Imate 903 robove; vsakega od teh lahko obarvamo na dva načina,« je pojasnil. »Torej dobiš 2⁹⁰³, kar je astronomsko veliko.«

Ko se velikost klike povečuje, postaja naloga določitve Ramseyevega števila samo še težja. Erdős je pošalil, da bi bila popolna vojna z matematično zahtevnimi nezemljani lažja kot poskus ugotovi R(6), kar je nekje med 102 in 165. Razpon negotovosti hitro raste: Po ocene, ki jih je zbral Stanisław Radziszowski, R(10) je lahko tako majhen kot 798 in velik kot 23,556. Toda cilji matematikov segajo daleč onkraj Ramseyevega števila 10. Želijo formulo, ki bo dala dobro oceno R(k), celo — ali še posebej — kadar k je izjemno velik.

"Ne poznam osebe v kombinatoriki, ki ne bi vsaj malo razmišljala o tem problemu," je dejal Wigderson. "Mislim, da je ta problem res poseben."

Red na sodišču

Frank Ramsey je bil eklektična, briljantna osebnost, ki je umrl, ko je bil star 26 let. Le nekaj tednov preden je umrl, je Zbornik London Mathematical Society objavljeno papir v katerem je predstavil Ramseyeva števila. To delo sploh ni bilo o grafih, ampak o problemu matematične logike. Ramsey je dokazal, da mora biti izjava, ki izpolnjuje določene pogoje, resnična vsaj nekaj časa. Eden od teh pogojev je bil, da obstaja veliko »vesolje« scenarijev za testiranje izjave. Kot odskočna deska k temu rezultatu je Ramsey pokazal, da je Ramseyevo število končno.

Pet let kasneje sta Erdős in Szekeres pokazala, da je Ramseyevo število k je manj kot 4^k. In 12 let po tem, Erdős je pokazal da je večji od približno $latex sqrt{2}^k$. Da bi to naredil, je izračunal možnosti, da graf z naključno obarvanimi robovi vsebuje enobarvno kliko. Ta "verjetnostna" tehnika je postala močno vplivna v teoriji grafov. Prav tako je ujel R(k) med dvema vratnicama, ki eksponentno naraščata: $latex sqrt{2}^k$ in $latex 4^k$.

Ko so minila desetletja, so številni matematiki poskušali zmanjšati vrzel med možnimi vrednostmi Ramseyevega števila. Nekaterim je uspelo: leta 1975 Joel Spencer podvojili spodnjo mejo. In vrsto člankov avtorja Conlon, Andrew Thomason in Ashwin Sah potisnil zgornjo mejo s faktorjem približno $latex 4^{log(k)^2}$ do leta 2020. Toda v primerjavi z velikostmi meja Ramseyevega števila so bile te prilagoditve majhne. Nasprotno pa vsako zmanjšanje na 4 v Erdősovi in ​​Szekeresovi formuli R(k) < 4^k bi bila eksponentna izboljšava, ki bi hitro naraščala k postane večji.

"Zdi se, kot da je samo ljubko vprašanje," je rekel Rob Morris, matematik na IMPA, brazilskem inštitutu za čisto in uporabno matematiko v Riu de Janeiru, ki je soavtor novega rezultata s Camposom, Griffithsom in Sahasrabudhejem. »To je nekoliko subtilno za ceniti. Toda ljudi res skrbi za to.« To je morda podcenjevanje. "Če bi to dokazali leta 1936, bi ljudje rekli, v redu, kaj je torej narobe?" je dejal Béla Bollobás, ki je bil doktorski svetovalec Morrisa in Sahasrabudheja na Univerzi v Memphisu. "Od takrat se je izkazalo, da je to zelo velik problem, saj je bilo v preteklih letih napisanih več tisoč člankov o različnih variantah Ramseyevega problema." Kot Liana Yepremyan, matematik z univerze Emory, je dejal: "Ramseyjeva števila ustvarjajo tisti most med kombinatoriko ter verjetnostjo in geometrijo."

Teorija iger

 Avgusta 2018 je bil Sahasrabudhe podoktorski sodelavec pri Morrisu pri IMPA. Upala sta, da bosta začela nov projekt z Griffithsom, ki poučuje na bližnji Papeški katoliški univerzi, ko članek Conlona pritegnil njihovo pozornost. Članek je orisal možno strategijo za eksponentno izboljšanje Ramseyevega števila. Griffiths, Morris in Sahasrabudhe so se začeli poigravati z idejo.

"Na začetku je bilo res razburljivo," se spominja Sahasrabudhe. Potrebovali so le približno mesec dni, je dejal, da so predstavili skico svojega argumenta.

Njihov načrt je bil graditi na idejah, uporabljenih v prvotnem dokazu Erdősa in Szekeresa, da je $latex R(k) < 4^k$. Če želite dokazati, da je Ramseyevo število največ $latex 4^k$, si predstavljajte igranje igre na celotnem grafu z vozlišči $latex 4^k$. Igra ima dva igralca. Najprej vaš nasprotnik obarva vsak rob rdeče ali modro, v upanju, da bo obarval robove na način, ki prepreči ustvarjanje enobarvne klike k vozlišč.

Ko vaš nasprotnik konča z barvanjem, je vaša naloga, da poiščete enobarvno kliko. Če ga najdete, zmagate.

Če želite zmagati v tej igri, lahko sledite preprosti strategiji. Pomaga razmišljati (metaforično) o razvrščanju vozlišč v dve vedri. Vozlišča v enem vedru bodo tvorila modro kliko, vozlišča v drugem pa rdečo kliko. Nekatera vozlišča bodo izbrisana, o njih ne bo nikoli več slišati. Na začetku sta obe vedri prazni in vsako vozlišče je kandidat za vstop v eno.

Začnite s katerim koli vozliščem, ki se vam zdi všeč. Nato poglejte povezovalne robove. Če je polovica ali več robov rdečih, izbrišite vse modre robove in vozlišča, s katerimi so povezani. Nato dajte svojo prvotno izbiro v "rdeče" vedro. Vsi rdeči robovi tega vozlišča so še vedno živi in ​​zdravi ter se oklepajo preostalega grafa iz notranjosti vedra. Če je več kot polovica robov modrega, analogno izbrišete rdeče robove in vozlišča ter ga postavite v modro vedro.

Ponavljajte, dokler ne ostane nobenih vozlišč. (Ker je graf končan, je vsako preostalo vozlišče na kateri koli točki povezano z obema vedroma, dokler ni postavljeno v enega od njiju.)

Ko končate, poglejte v vedra. Ker je vozlišče šlo v rdeče vedro šele potem, ko so bili njegovi modri sosedje izločeni, so vsa vozlišča v rdečem vedru povezana z rdečimi robovi – tvorijo rdečo kliko. Podobno modro vedro tvori modro kliko. Če ima vaš izvirni graf vsaj $latex 4^k$ vozlišč, je mogoče dokazati, da mora eno od teh veder vsebovati vsaj k vozlišč, kar zagotavlja monokromatsko kliko v izvirnem grafu.

Ta argument je pameten in eleganten, vendar vam omogoča, da zgradite dve kliki - eno modro in eno rdečo - čeprav v resnici potrebujete samo eno. Bolj učinkovito bi bilo, če bi vedno rdeča, je pojasnil Conlon. Pri tej strategiji bi pri vsakem koraku izbrali vozlišče, izbrisali njegove modre robove in ga vrgli v rdeče vedro. Rdeče vedro bi se nato hitro napolnilo in nabrali bi rdečo kliko k vozlišča v polovici časa.

Toda vaša strategija mora delovati za vsako rdeče-modro barvo in težko je vedeti, ali lahko vedno najdete vozlišče z veliko rdečimi robovi. Če torej sledite Conlonovemu predlogu, tvegate, da boste naleteli na vozlišče, ki nima skoraj nobenih rdečih robov. To bi vas prisililo, da naenkrat izbrišete ogromen del grafa, zaradi česar bi morali sestaviti svojo kliko, preden vam zmanjka vozlišč. Za izvedbo Conlonovega predloga so morali Griffiths, Morris in Sahasrabudhe dokazati, da se je temu tveganju mogoče izogniti.

Izpit z odprto knjigo

Pri posodabljanju svojega igranja so Griffiths, Morris in Sahasrabudhe sledili nekoliko bolj zaobljeni poti. Namesto da bi zgradili monokromatsko kliko neposredno z metanjem vozlišč v njihovih rdečih in modrih vedrih, so se najprej osredotočili na izgradnjo strukture, imenovane rdeča knjiga.

V teoriji grafov je knjiga sestavljena iz dveh delov: obstaja enobarvna klika, imenovana »hrbtenica«, in druga, ločena skupina vozlišč, imenovana »strani«. V rdeči knjigi so vsi robovi, ki povezujejo vozlišča znotraj hrbtenice, rdeči, prav tako robovi, ki povezujejo hrbtenico s stranmi. Robovi, ki povezujejo vozlišča znotraj strani, pa so lahko poljubne kombinacije barv. Conlon je v svojem prispevku iz leta 2018 opozoril, da če najdete rdečo kliko znotraj strani knjige, jo lahko združite s hrbtom, da dobite večjo rdečo kliko. To vam omogoča, da iskanje velike rdeče klike razdelite na dve lažji iskanji. Najprej poiščite rdečo knjigo. Nato poiščite klik na straneh knjige.

Griffiths, Morris in Sahasrabudhe so želeli prilagoditi zmagovalni algoritem tako, da je namesto rdeče klike zgradil rdečo knjigo. Čeprav so se za ta načrt odločili le nekaj tednov po začetku svojega projekta, so trajala leta, da bi začel delovati. Še vedno so morali preprečiti grožnjo, da bodo izgubili vse svoje rdeče robove.

"Dolgo smo bili obtičali," je dejal Campos, ki se je projektu pridružil leta 2021.

Letos januarja so se štirje matematiki dogovorili, da bodo prešli na drugo različico problema. Ta različica se sliši bolj zapletena, vendar se je izkazala za lažjo.

Ves čas je bila ekipa osredotočena na Ramseyevo število R(k), znano tudi kot "diagonalno" Ramseyevo število. Graf velikosti R(k) mora vsebovati k vozlišča, ki so vsa povezana z robovi iste barve, vendar ni pomembno, ali je ta barva rdeča ali modra. Po drugi strani pa "nediagonalno" Ramseyevo število R(k, l) meri, kako velik mora biti graf, preden vsebuje bodisi rdečo kliko z k vozlišča ali modra klika z l vozlišča. Namesto da bi se še naprej ukvarjali z diagonalnim problemom, se je skupina odločila poskusiti z nediagonalno različico. To se je izkazalo za razodetje.

"Dolgo časa se je zdelo, da so bila vsa vrata, na katera ste pritisnili, bodisi zapahnjena ali vsaj precej težko priti skozi," je dejal Griffiths. »In po tej spremembi si se preprosto počutil, kot da so vsa vrata odprta. Nekako se je zdelo, da vse deluje." V nediagonalni različici so našli način za brisanje množice modrih robov naenkrat po določenem protokolu, kar je povečalo gostoto rdečih robov in vodilo do izboljšane meje nediagonalnega Ramseyevega števila. Ta metoda, imenovana argument "prirastka gostote", je bila prej uporabljena za reševanje drugi pomembni problemi kombinatorike, vendar ni bil uporabljen pri problemu Ramseyevega števila.

Štirje matematiki so nato uporabili novo mejo nediagonalnega Ramseyjevega števila, da so očistili pot diagonalnemu rezultatu. Do začetka februarja so končno znižali mejo Ramseyevega števila za eksponentni faktor, dosežek, ki so ga matematiki iskali skoraj stoletje. In to jim je uspelo s posodobitvijo iste argumentacije, ki sta jo leta 1935 podala Erdős in Szekeres.

Epsilon, Epsilon

Po pogovorih 16. marca so udeleženci začeli potrjevati govorice. Fotografije iz Sahasrabudhejevega govora so krožile po telefonskih klicih in zasebnih sporočilih – celo v nejasna, a sugestivna objava na blogu matematika Gila Kalaija. Campos, Griffiths, Sahasrabudhe in Morris so trdili, da so dokazali, da je $latex R(k) < 3.993^k$. Tisto noč so štirje avtorji svoj prispevek objavili na spletu, ki matematikom omogoča, da si sami ogledajo nov dokaz.

"Mislim, da mnogi od nas v bistvu niso pričakovali takšne izboljšave v življenju," je dejal Matija Bucić, matematik na Univerzi Princeton in Inštitutu za napredne študije. "Mislim, da je to absolutno neverjeten rezultat."

Številni strokovnjaki upajo, da bo s podrto eksponentno oviro hitro sledil večji napredek. Avtorji novega članka namerno niso potisnili svoje metode do meja, da bi se izognili zameglitvi svojega argumenta z nepotrebnimi podrobnostmi. "Zelo me zanima, kako daleč lahko gre metoda, ker nimam pojma," je dejal Campos.

»To je popolnoma genialen, absolutno čudovit dokaz in resničen preboj. Tako zdaj pričakujem, da se bodo zapornice odprle,« je dejal Bollobás. »Prepričan sem, da bo čez tri leta razprava tekla o možnih izboljšavah. Ali lahko izboljšamo 3.993 na 3.9? Mogoče na 3.4? Kaj pa 3?"

Novi dokaz obsega 56 strani in potrebni bodo tedni, da bo kombinatorična skupnost v celoti preverila vsako podrobnost. So pa kolegi optimistični. »Ta skupina avtorjev so zelo resni ljudje. In to so ljudje, ki so res, zelo dobri v zelo tehničnih stvareh,« je dejal Wigderson.

Ko gre za njegove sodelavce, se Griffiths strinja. »Privilegij je delati z briljantnimi ljudmi, kajne? In mislim, da sem za to zelo hvaležen,« je dejal. "Če bi to prepustili meni, bi morda potreboval še pet let, da bi uredil podrobnosti."