Erittäin suuri pieni harppaus graafiteoriassa

Maaliskuun 15. päivänä kiehtovat seminaariilmoitukset lähettivät jyrinää kombinatoriikan, laskennan matemaattisen tutkimuksen, alalle. Kolme yhteistyökumppania aikoi pitää koordinoidut keskustelut seuraavana päivänä. Julian Sahasrabudhe puhuisi matemaatikoille Cambridgessa Englannissa Simon Griffiths jakaisi uutisen Rio de Janeirossa ja Marcelo Campos São Paulossa. Kaikilla kolmella puheella oli identtiset otsikot ja salaperäiset, kahden lauseen abstraktit, joissa viitattiin "äskettäiseen edistykseen Erdősin vanhan ongelman parissa". Vuonna 1996 kuollut unkarilainen matemaatikko Paul Erdős poseerasi satoja ongelmia hänen uransa aikana kombinatoristit arvasivat nopeasti erityiskysymyksen, josta trio aikoi puhua. Huhut pyörivät Ramsey-luvusta, joka on yksi vaikeimmin laskettavissa olevista suureista koko matematiikan alueella.

Ramsey-luvut ovat synnyttäneet kokonaisen tieteenalan nimeltä Ramsey-teoria, joka etsii väistämättömiä malleja valtavasta valikoimasta järjestelmiä.

Oletetaan esimerkiksi, että yrität jakaa kaikki kokonaisluvut useiden segmenttien kesken ja haluat välttää sijoittamasta tasaisin välein olevia numerosarjoja mihinkään ryhmään. Ramseyn teoria osoittaa, että epäonnistut (ellei sinulla ole äärettömän monta ämpäriä). Teoriaa voidaan soveltaa melkein mihin tahansa, mitä voit laskea. Sen keskeinen opetus on, että "et voi luoda täysin kaoottista järjestelmää", sanoi Benny Sudakov, matemaatikko Sveitsin Federal Institute of Technology Zürichistä.

Ramsey-luku ilmaisee, kuinka suuri paradigmaattisen esimerkin on oltava, ennen kuin tiettyjä malleja väistämättä syntyy. Mutta keskeisyydestään huolimatta kukaan ei ole pystynyt laskemaan Ramsey-lukua kaikille paitsi yksinkertaisimmat tapaukset. Parasta, mitä he ovat voineet tehdä, on löytää rajat (tai rajat) sille, mitä se voi olla. Silloinkin Erdősin ja yhteistyökumppanin lähes sata vuotta sitten asettama yläraja oli hädin tuskin horjunut.

Sitten 15. maaliskuuta järjestetyissä seminaareissa ja myöhemmin samana iltana julkaistussa paperissa tutkijat ilmoittivat parantaneensa Ramseyn luvun ylärajaa eksponentiaalisesti.

"Olin lattialla", sanoi Yuval Wigderson, matemaatikko Tel Avivin yliopistosta kuultuaan uudesta tuloksesta. "Minua ravistelin kirjaimellisesti puolen tunnin tai tunnin ajan."

Party Lines

Ramseyn teoria kysyy yleisimmin joko kokonaislukuja tai kaavioita koskevia kysymyksiä. Graafilla tarkoitetaan tässä yhteydessä pistekokoelmia, joita kutsutaan solmuiksi ja jotka on yhdistetty reunoiksi kutsutuilla viivoilla ja joilla voi olla ominaisuuksia, kuten pituus tai - kuten Ramsey-lukujen tapauksessa - väri.

Täydellinen kaavio on sekä monimutkainen että yksinkertainen – jokainen solmu on yhteydessä jokaiseen toiseen solmuun. Ramsey-luku kuvaa kuinka monta solmua täydellisen graafin täytyy sisältää, jotta se pakotetaan käyttämään tiettyä rakennetta. Oletetaan, että kokonaisen kaavion reunoilla on yksi kahdesta väristä: punainen tai sininen. Ja sanotaan, että yrität värittää reunat tavalla, joka välttää solmuryhmän yhdistämisen samanväristen reunojen kanssa. Vuonna 1930 Frank Ramsey osoitti, että jos graafi on tarpeeksi suuri, on mahdotonta välttää luomasta sitä, mitä matemaatikot kutsuvat monokromaattiseksi klikeiksi - ryhmäksi solmuja, joiden yhteiset reunat ovat joko kokonaan punaisia ​​tai kokonaan sinisiä.

Kuinka suuri tarkalleen ottaen graafin pitää olla, ennen kuin yksivärinen klikki pakotetaan esiin? Vastaus riippuu klikin koosta. Ramsey osoitti, että on olemassa numero, jota nyt kutsutaan Ramseyn numeroksi ja joka edustaa vähimmäismäärää solmuja, joille tietyn kokoisen monokromaattisen klikkin on oltava olemassa riippumatta siitä, kuinka reunat ovat värillisiä.

Mutta Ramseyn numeron kokoa on vaikea määrittää. Vuonna 1935, viisi vuotta sen jälkeen, kun Ramsey osoitti sen olemassaolon, Erdős ja George Szekeres esittivät uuden, tiukemman ylärajan sille, kuinka suuri Ramsey-luku on tietyn kokoiselle klikkille. Mutta sen jälkeen matemaatikot ovat tuskin kyenneet parantamaan Erdősin ja Szekeresin laskelmia.

Saadaksesi paremman intuition siitä, mitä tämä tarkoittaa, harkitse klassista esimerkkiä, jossa solmut edustavat vieraita juhlissa. Väritä minkä tahansa kahden vieraan välinen reuna punaiseksi, jos he ovat tavanneet aiemmin, ja siniseksi, jos he eivät ole tavanneet. Voit valita minkä tahansa klikkin koon – kutsu tarpeeksi ihmisiä juhliin, etkä voi välttää kutsumasta joukko ihmisiä, jotka kaikki tuntevat toisensa (klikki sanan useissa merkityksissä) tai kutsumasta joukko ihmisiä, jotka ole koskaan ennen tavannut.

"Yksinkertaisin asia, joka voi olla kaaviossa, on monokromaattinen klikki", sanoi Maria Chudnovski, matemaatikko Princetonin yliopistosta. ”On hämmästyttävää, että jokaisesta valtavasta kaaviosta löytyy iso sellainen. Se ei ole täysin selvää."

Ensimmäiset Ramsey-luvut ovat suhteellisen yksinkertaisia ​​laskea. Oletetaan, että haluat tietää pienimmän graafin koon, jonka täytyy väistämättä pitää sisällään koon kaksi klikkausta eli R(2) matemaatikoille. Koska täydellinen graafi, jossa on kaksi solmua, on vain kaksi reunalla yhdistettyä solmua ja tämän reunan on oltava joko punainen tai sininen, R(2) on 2. Yleisemmin R(k), tai Ramseyn numero k, on solmujen vähimmäismäärä, jonka ylittyessä kaaviossa ei voida välttää koon kokoista klikkausta k.

Ei ole niin vaikeaa osoittaa, että Ramsey-luku 3-koon klikkille eli R(3) on 6 (katso kuvaa). Mutta vasta vuonna 1955 R(4) merkittiin arvoon 18. R(5) on edelleen tuntematon – se on vähintään 43 eikä suurempi kuin 48. Vaikka nämä luvut ovat pieniä, kaikkien mahdollisten väritysten seulominen ei onnistu. David Conlon Kalifornian teknologiainstituutista sanoi. Harkitse väritysten määrää täydellisessä kaaviossa, jossa on 43 solmua. "Sinulla on 903 reunaa; jokainen niistä voidaan värjätä kahdella tavalla", hän selitti. "Joten saat 2⁹⁰³, joka on vain tähtitieteellisesti suuri."

Klikin koon kasvaessa Ramseyn numeron naulaaminen vain vaikeutuu. Erdős vihjaili, että sota matemaattisesti vaativien alienien kanssa olisi helpompaa kuin yrittää selvittää R(6), joka on jossain 102 ja 165 välillä. Epävarmuusalue kasvaa nopeasti: Stanisław Radziszowskin laatimat arviot, R(10) voi olla niinkin pieni kuin 798 ja jopa 23,556 10. Mutta matemaatikoiden tavoitteet ylittävät paljon Ramseyn luvun XNUMX. He haluavat kaavan, joka antaa hyvän arvion R(k), jopa - tai erityisesti - kun k on erittäin suuri.

"En tiedä kombinatoriikasta henkilöä, joka ei olisi ajatellut tätä ongelmaa edes vähän", Wigderson sanoi. "Tämä ongelma on mielestäni todella erityinen."

Määräys tuomioistuimessa

Frank Ramsey oli eklektinen, loistava hahmo, joka kuoli ollessaan 26-vuotias. Vain viikkoja ennen kuolemaansa, Proceedings of the London Mathematical Society julkaistu paperi jossa hän esitteli Ramsey-numerot. Tuo työ ei ollut edes kaavioista, vaan matemaattisen logiikan ongelmasta. Ramsey osoitti, että väitteen, joka täyttää tietyt ehdot, on oltava totta ainakin osan ajasta. Yksi näistä ehdoista oli, että on olemassa suuri ”universumi” skenaarioita väittämän testaamiseksi. Ponnahduslautana tähän tulokseen Ramsey osoitti, että Ramseyn luku on äärellinen.

Viisi vuotta myöhemmin Erdős ja Szekeres osoittivat, että Ramsey-luku k on alle 4^k. Ja 12 vuotta sen jälkeen Erdős näytti että se on suurempi kuin noin $latex sqrt{2}^k$. Tätä varten hän laski todennäköisyyden, että satunnaisesti väritetyillä reunoilla varustettu graafi sisältää monokromaattisen klikkin. Tästä "todennäköisyyspohjaisesta" tekniikasta tuli valtavasti vaikutus graafiteoriassa. Se jäi myös loukkuun R(k) kahden eksponentiaalisesti kasvavan maalitolpan välillä: $lateksi sqrt{2}^k$ ja $lateksi 4^k$.

Vuosikymmenten liukuessa monet matemaatikot yrittivät kaventaa Ramseyn luvun mahdollisten arvojen välistä kuilua. Jotkut onnistuivat: Vuonna 1975 Joel Spencer kaksinkertaisti alarajan. Ja sarjan papereita Conlon, Andrew Thomason ja Ashwin Sah painoi ylärajaa alas kertoimella noin $lateksi 4^{log(k)^2}$ vuoteen 2020 mennessä. Mutta Ramsey-luvun rajojen kokoihin verrattuna nämä säädöt olivat pieniä. Sitä vastoin mikä tahansa pelkistys 4:ään Erdősin ja Szekeresin kaavassa R(k) < 4^k olisi eksponentiaalinen parannus, joka kasvaisi nopeasti k kasvaa.

"Se vaikuttaa vain suloiselta kysymykseltä", sanoi Rob Morris, matemaatikko IMPA:ssa, Brasilian puhtaan ja sovelletun matematiikan instituutissa, Rio de Janeirossa, joka kirjoitti uuden tuloksen yhdessä Camposin, Griffithin ja Sahasrabudhen kanssa. "Se on hieman hienovaraista arvostaa. Mutta ihmiset todella välittävät siitä." Tämä on mahdollisesti aliarviointi. "Jos he olisivat todistaneet sen vuonna 1936, ihmiset olisivat sanoneet: okei, joten mikä on iso juttu?" sanoi Béla Bollobás, joka oli Morrisin ja Sahasrabudhen tohtoriohjaaja Memphisin yliopistossa. "Sittemmin on todistettu, että se on erittäin suuri ongelma, koska vuosien aikana on kirjoitettu useita tuhansia artikkeleita Ramseyn ongelman eri muunnelmista." Kuten Liana YepremyanEmoryn yliopiston matemaatikko sanoi: "Ramseyn luvut luovat sillan kombinatoriikan ja todennäköisyyden ja geometrian välille."

Peliteoria

 Elokuussa 2018 Sahasrabudhe oli Morrisin alainen tutkijatohtori IMPA:ssa. He toivoivat voivansa aloittaa uuden projektin Griffithsin kanssa, joka opettaa läheisessä paavillisessa katolisessa yliopistossa, kun Conlonin paperi kiinnitti heidän huomionsa. Paperi hahmotteli mahdollisen strategian saada eksponentiaalinen parannus Ramseyn numeroon. Griffiths, Morris ja Sahasrabudhe alkoivat leikkiä ajatuksella.

"Se oli todella jännittävää alussa", Sahasrabudhe muisteli. Heiltä meni vain noin kuukausi, hän sanoi, että he laativat luonnoksen väitteestään.

Heidän suunnitelmansa oli rakentaa ajatuksia, joita käytettiin Erdősin ja Szekeresin alkuperäisessä todisteessa, että $lateksi R(k) < 4^k$. Todistaaksesi, että Ramsey-luku on korkeintaan $lateksi 4^k$, kuvittele pelaavasi peliä täydellisellä kaaviolla, jossa on $lateksi 4^k$ solmuja. Pelissä on kaksi pelaajaa. Ensin vastustajasi värjää jokaisen reunan joko punaiseksi tai siniseksi toivoen voivansa värjätä reunat tavalla, joka välttää monokromaattisen klikin muodostumisen. k solmuja.

Kun vastustajasi on värittänyt, sinun tehtäväsi on etsiä yksivärinen klikki. Jos löydät sellaisen, voitat.

Voit voittaa tämän pelin noudattamalla yksinkertaista strategiaa. Se auttaa ajattelemaan (metaforisesti) solmujen lajittelua kahteen ämpäriin. Yhdessä ämpärissä olevat solmut muodostavat sinisen klikkin ja toisen ryhmän solmut punaisen klikkin. Jotkut solmut poistetaan, eikä niistä enää koskaan kuulla. Alussa molemmat kauhat ovat tyhjiä, ja jokainen solmu on ehdokas siirtyä jompaankumpaan.

Aloita mistä tahansa solmusta, joka osuu mieleesi. Katso sitten liitosreunoja. Jos puolet tai useampi reunoista on punaisia, poista kaikki siniset reunat ja solmut, joihin ne on liitetty. Laita sitten alkuperäinen valintasi "punaiseen" ämpäriin. Kaikki tämän solmun punaiset reunat ovat edelleen elossa ja voivat hyvin, ja ne tarttuvat graafin muuhun osaan kauhan sisältä. Jos yli puolet reunoista on sinisiä, poistat vastaavasti punaiset reunat ja solmut ja laitat ne siniseen ämpäriin.

Toista, kunnes sinulla ei ole enää solmuja. (Koska kaavio on valmis, jokainen jäljellä oleva solmu missä tahansa kohdassa on yhdistetty molempiin ryhmiin, kunnes se sijoitetaan johonkin niistä.)

Kun olet valmis, katso kauhojen sisään. Koska solmu meni punaiseen ämpäriin vasta sen jälkeen, kun sen siniset naapurit oli eliminoitu, kaikki punaisen kauhan solmut on yhdistetty punaisilla reunoilla - ne muodostavat punaisen klikkin. Samoin sininen ämpäri muodostaa sinisen klikkin. Jos alkuperäisessä kaaviossasi on vähintään $lateksi 4^k$ solmua, on mahdollista todistaa, että yhdessä näistä ryhmistä on oltava vähintään k solmut, mikä takaa monokromaattisen klikkin alkuperäisessä kaaviossa.

Tämä argumentti on fiksu ja tyylikäs, mutta se saa sinut rakentamaan kaksi klikkausta – yhden sinisen ja toisen punaisen – vaikka tarvitset vain yhden. Olisi tehokkaampaa mennä aina punaiseksi, Conlon selitti. Tämän strategian mukaan valitset solmun jokaisessa vaiheessa, pyyhit sen siniset reunat ja heität sen punaiseen ämpäriin. Sitten punainen ämpäri täyttyisi nopeasti, ja keräät punaisen klikkauksen k solmuja puolessa ajassa.

Mutta strategiasi on toimittava minkä tahansa puna-sinisen värityksen kanssa, ja on vaikea tietää, löydätkö aina solmun, jossa on paljon punaisia ​​reunoja. Joten Conlonin ehdotuksen noudattaminen on vaarassa törmätä solmuun, jossa ei ole juuri lainkaan punaisia ​​reunoja. Tämä pakottaisi sinut poistamaan suuren osan kaaviosta kerralla, jolloin sinun on pakko rakentaa klikkausta ennen kuin solmut loppuvat. Conlonin ehdotuksen toteuttamiseksi Griffithsin, Morrisin ja Sahasrabudhen oli todistettava, että tämä riski oli vältettävissä.

Avoimen kirjan koe

Päivittäessään peliään Griffiths, Morris ja Sahasrabudhe seurasivat hieman mutkikkaampaa reittiä. Sen sijaan, että he olisivat rakentaneet monokromaattista klikkia suoraan heittämällä solmuja punaisiin ja sinisiin ämpäriinsä, he keskittyivät ensin punaiseksi kirjaksi kutsutun rakenteen rakentamiseen.

Graafiteorian mukaan kirja koostuu kahdesta osasta: siellä on yksivärinen klikki, jota kutsutaan "selkärangaksi", ja toinen, erillinen solmuryppä, jota kutsutaan "sivuiksi". Punaisessa kirjassa kaikki selkärangan solmuja yhdistävät reunat ovat punaisia, samoin kuin reunat, jotka yhdistävät selkärangan sivuihin. Sivujen sisällä olevia solmuja yhdistävät reunat voivat kuitenkin olla mitä tahansa väriyhdistelmiä. Conlon oli todennut vuoden 2018 artikkelissaan, että jos löydät punaisen klikkin kirjan sivuilta, voit yhdistää sen selkärangan kanssa saadaksesi suuremman punaisen klikkin. Tämän avulla voit jakaa suuren punaisen klikkin haun kahdeksi helpommaksi hauksi. Etsi ensin punainen kirja. Etsi sitten klikkausta kirjan sivuilta.

Griffiths, Morris ja Sahasrabudhe halusivat säätää pelin voittanutta algoritmia niin, että se rakensi punaisen kirjan punaisen klikkin sijaan. Vaikka he päätyivät tähän suunnitelmaan vain viikkoja projektissaan, kestäisi vuosia saada se toimimaan. Heidän oli silti vältettävä uhkaa menettää kaikki punaiset reunansa.

"Olimme jumissa erittäin pitkään", sanoi Campos, joka liittyi projektiin vuonna 2021.

Tänä tammikuussa neljä matemaatikkoa sopivat vaihtavansa ongelman toiseen versioon. Tämä versio kuulostaa monimutkaisemmalta, mutta se osoittautui helpommaksi.

Koko ajan joukkue oli keskittynyt Ramseyn numeroon R(k), joka tunnetaan myös nimellä "diagonaalinen" Ramsey-numero. Kuvaaja, jonka koko on R(k) täytyy sisältää k solmut, jotka kaikki yhdistetään samanväristen reunojen kautta, mutta sillä ei ole väliä, onko tämä väri punainen vai sininen. Toisaalta "pois diagonaalinen" Ramseyn numero R(k, l) mittaa kuinka suuri kaavion on oltava ennen kuin se sisältää joko punaisen klikkin k solmut tai sininen klikki l solmut. Sen sijaan, että he olisivat jatkaneet diagonaaliongelman etsimistä, ryhmä päätti kokeilla diagonaalista poikkeavaa versiota. Tämä osoittautui paljastavaksi.

"Pitkän aikaa tuntui, että jokainen työntämäsi ovi oli joko pultattu kiinni tai ainakin melko vaikea päästä läpi", Griffiths sanoi. ”Ja tuon muutoksen jälkeen sinusta vain tuntui, että jokainen ovi oli auki. Jotenkin kaikki näytti toimivan." Diagonaalista poikkeavassa versiossa he löysivät tavan poistaa joukon sinisiä reunoja kerralla tietyn protokollan mukaisesti, mikä lisäsi punaisten reunojen tiheyttä ja johti parantuneeseen rajoitukseen diagonaalisen Ramsey-luvun ulkopuolella. Tätä menetelmää, jota kutsutaan "tiheyden lisäyksen" argumentiksi, oli aiemmin käytetty ratkaisemiseen muita tärkeitä kombinatoriikan ongelmia, mutta sitä ei ollut käytetty Ramseyn numeroongelmaan.

Neljä matemaatikkoa käyttivät sitten diagonaalista poikkeavan Ramsey-luvun uutta sidontaa raivaamaan tietä diagonaalitulokselle. Helmikuun alkuun mennessä he olivat lopulta alentaneet Ramseyn luvun rajaa eksponentiaalisella kertoimella, saavutusta matemaatikot olivat pyrkineet lähes vuosisadan ajan. Ja he tekivät sen modernisoimalla samaa argumentointia, jonka Erdős ja Szekeres olivat esittäneet vuonna 1935.

Epsilon, Epsilon

Neuvottelujen jälkeen 16. maaliskuuta osallistujat alkoivat vahvistaa huhuja. Kuvia Sahasrabudhen puheesta levisi puheluiden ja yksityisviestien kautta – jopa a epämääräinen mutta vihjaileva viesti matemaatikko Gil Kalain blogissa. Campos, Griffiths, Sahasrabudhe ja Morris väittivät osoittaneensa, että $lateksi R(k) < 3.993^k$. Sinä iltana neljä kirjailijaa julkaisi paperinsa nettiin, jolloin matemaatikot voivat nähdä uuden todisteen itse.

"Uskon, että monet meistä eivät odottaneet näkevänsä tällaista parannusta elämänsä aikana", sanoi Matija Bucić, matemaatikko Princetonin yliopistossa ja Institute for Advanced Studyssa. "Mielestäni se on aivan uskomaton tulos."

Monet asiantuntijat ovat toiveikkaita, että eksponentiaalisen esteen kaatumisen myötä edistystä seuraa nopeasti. Uuden artikkelin kirjoittajat eivät tarkoituksella työntäneet menetelmäään äärirajoihinsa välttääkseen väitteensä hämärtymisen tarpeettomilla yksityiskohdilla. "Olen erittäin kiinnostunut siitä, kuinka pitkälle menetelmä voi todella mennä, koska minulla ei ole aavistustakaan", Campos sanoi.

”Se on äärimmäisen nerokas, aivan upea todiste ja todellinen läpimurto. Joten nyt odotan, että tulvaportit avataan", Bollobás sanoi. ”Olen vakuuttunut siitä, että kolmen vuoden kuluttua keskustelussa käydään mahdollisista parannuksista. Voimmeko parantaa 3.993:sta 3.9:ään? Ehkä 3.4? Ja entä 3?"

Uusi todistus on 56-sivuinen, ja kestää viikkoja, ennen kuin kombinatoriikkayhteisö tarkistaa jokaisen yksityiskohdan täysin. Mutta kollegat ovat optimistisia. "Tämä kirjailijoiden ryhmä, he ovat erittäin vakavia ihmisiä. Ja he ovat ihmisiä, jotka ovat todella, todella hyviä erittäin teknisissä asioissa”, Wigderson sanoi.

Mitä tulee hänen yhteistyökumppaniinsa, Griffiths on samaa mieltä. ”On etuoikeus työskennellä loistavien ihmisten kanssa, eikö niin? Ja luulen, että olen siitä hyvin kiitollinen", hän sanoi. "Jos he olisivat jättäneet asian minulle, minulla olisi ehkä mennyt vielä viisi vuotta saadakseni yksityiskohdat oikein."