Väga suur väike samm edasi graafikuteoorias

15. märtsil saatsid intrigeerivad seminarikuulutused läbi kombinatoorika, loendamise matemaatilise õppe. Kolm kaastöötajat kavatsesid järgmisel päeval pidada kooskõlastatud kõnesid. Julian Sahasrabudhe pöörduks Inglismaal Cambridge'i matemaatikute poole Simon Griffiths jagaks uudist Rio de Janeiros ja Marcelo Campos São Paulos. Kõigil kolmel kõnel olid identsed pealkirjad ja salapärased kahelauselised kokkuvõtted, mis viitasid "hiljutisele edule Erdősi vana probleemi lahendamisel". Samal ajal kui 1996. aastal surnud ungari matemaatik Paul Erdős poseeris sadu probleeme tema karjääri jooksul mõistsid kombinaatorid kiiresti selgeks konkreetse teema, millest kolmik kavatses rääkida. Kuulujutud keerlesid Ramsey numbri kohta, mis on üks kõige raskemini arvutatavaid suurusi kogu matemaatikas.

Ramsey numbrid on loonud terve distsipliini nimega Ramsey teooria, mis otsib vältimatuid mustreid paljudes süsteemides.

Oletame näiteks, et proovite jaotada kõik täisarvud mitme salga vahel ja soovite vältida ühtlase vahega arvujadade paigutamist ühtedesse gruppidesse. Ramsey teooria näitab, et sa kukud läbi (kui sul pole lõpmatult palju ämbreid). Teooriat saab rakendada kõigele, mida saate lugeda. Selle keskne õppetund on see, et "täiesti kaootilist süsteemi ei saa luua," ütles Šveitsi Zürichi Tehnoloogiainstituudi matemaatik Benny Sudakov.

Ramsey arv kvantifitseerib, kui suur peab olema paradigmaatiline näide, enne kui teatud mustrid paratamatult esile kerkivad. Kuid hoolimata selle kesksusest ei ole keegi suutnud Ramsey arvu arvutada kõigi jaoks, välja arvatud lihtsamaid juhtumeid. Parim, mida nad on suutnud teha, on leida piirangud (või piirid), mis see võib olla. Isegi siis oli Erdősi ja kaastöölise peaaegu sajand tagasi kehtestatud ülempiir vaevu liikunud.

Seejärel teatasid teadlased 15. märtsi seminaridel ja hiljem samal õhtul postitatud artiklis, et nad on Ramsey numbri ülemist piiri eksponentsiaalselt parandanud.

"Ma olin põrandal," ütles Yuval Wigderson, Tel Avivi ülikooli matemaatik, kuuldes uuest tulemusest. "Ma värisesin sõna otseses mõttes pool tundi kuni tund."

Parteiliinid

Ramsey teooria esitab kõige sagedamini küsimusi kas täisarvude või graafikute kohta. Graaf viitab selles kontekstis punktide kogumitele, mida nimetatakse sõlmedeks ja mis on ühendatud joontega, mida nimetatakse servadeks ja millel võivad olla sellised omadused nagu pikkus või – nagu Ramsey numbrite puhul – värv.

Terviklik graafik on ühtaegu keeruline ja lihtne – iga sõlm on ühendatud iga teise sõlmega. Ramsey arv kirjeldab, mitu sõlme peab täielik graafik sisaldama, et sellel oleks teatud struktuur. Oletame, et terve graafiku servadele on määratud üks kahest värvist: punane või sinine. Ja oletame, et proovite servi värvida viisil, mis väldib sõlmede rühma ühendamist sama värvi servadega. 1930. aastal tõestas Frank Ramsey, et kui graaf on piisavalt suur, on võimatu vältida seda, mida matemaatikud nimetavad monokromaatiliseks klikiks – sõlmede rühma, mille ühised servad on kas üleni punased või üleni sinised.

Kui suur täpselt peab graafik olema, enne kui monokromaatiline klikk on sunnitud tekkima? Vastus oleneb kliki suurusest. Ramsey näitas, et on olemas number, mida nüüd nimetatakse Ramsey numbriks ja mis tähistab minimaalset sõlmede arvu, mille jaoks peab eksisteerima teatud suurusega monokromaatiline klikk, olenemata servade värvist.

Kuid Ramsey numbri suurust on raske kindlaks teha. Aastal 1935, viis aastat pärast seda, kui Ramsey näitas selle olemasolu, andsid Erdős ja George Szekeres uue, rangema ülempiiri selle kohta, kui suur on Ramsey arv teatud suurusega kliki kohta. Kuid sellest ajast peale on matemaatikud vaevu suutnud Erdősi ja Szekeresi arvutusi parandada.

Parema intuitsiooni saamiseks, mida see tähendab, kaaluge klassikalist näidet, kus sõlmed tähistavad külalisi peol. Värvige kahe külalise vaheline serv punaseks, kui nad on varem kohtunud, ja siniseks, kui nad pole veel kohtunud. Saate valida mis tahes suuruse, mis teile meeldib – kutsuge peole piisavalt inimesi ja te ei saa vältida ei kutsumast rühma inimesi, kes kõik üksteist tunnevad (selle sõna mitmes tähenduses klikk) ega kutsumast inimesi, kes pole kunagi varem kohtunud.

"Kõige lihtsam asi, mis teil graafikus võib olla, on monokromaatiline klikk," ütles Maria Tšudnovski, Princetoni ülikooli matemaatik. "See on omamoodi hämmastav, et igal tohutul graafikul võite leida suure graafiku. See pole täiesti selge."

Esimesi Ramsey arvusid on suhteliselt lihtne arvutada. Oletame, et soovite teada väikseima graafiku suurust, mis peab vältimatult hoidma kahe suurust klikki või matemaatikute arvates R(2). Kuna kahe sõlmega täielik graaf on vaid kaks servaga ühendatud sõlme ja see serv peab olema kas punane või sinine, on R(2) 2. Üldisemalt R(k) või Ramsey number k, on minimaalne sõlmede arv, millest suurem graafik ei saa vältida suure kliki sisaldamist k.

Pole nii raske näidata, et Ramsey arv 3 suuruse kliki või R(3) jaoks on 6 (vt graafikut). Kuid alles 1955. aastal fikseeriti R(4) väärtuseks 18. R(5) jääb teadmata – see on vähemalt 43 ja mitte suurem kui 48. Kuigi need arvud on väikesed, on kõigi võimalike värvide väljasõelumine võimatu David Conlon California Tehnoloogiainstituudist. Mõelge värvide arvule 43 sõlmega terviklikul graafikul. "Sul on 903 serva; kõiki neid saab värvida kahel viisil, ”selgitas ta. "Nii et sa saad 2⁹⁰³, mis on lihtsalt astronoomiliselt suur.

Kliki suuruse kasvades muutub Ramsey numbri tabamine ainult raskemaks. Erdős ironiseeris, et täielik sõda matemaatiliselt nõudlike tulnukatega oleks lihtsam kui katse mõtle välja R(6), mis on kuskil 102 ja 165 vahel. Määramatuse vahemik kasvab kiiresti: Vastavalt hinnangud, mille koostas Stanisław Radziszowski, R(10) võib olla nii väike kui 798 ja koguni 23,556 10. Kuid matemaatikute eesmärgid ulatuvad palju kaugemale kui Ramsey arv XNUMX. Nad tahavad valemit, mis annaks hea hinnangu R(k), isegi - või eriti - kui k on äärmiselt suur.

"Ma ei tea kombinatoorika alal inimest, kes poleks sellele probleemile vähemalt natukenegi mõelnud," ütles Wigderson. "See probleem on minu arvates tõesti eriline."

Kohtumäärus

Frank Ramsey oli eklektiline ja särav kuju, kes suri 26-aastaselt. Vaid nädalad enne tema surma, Londoni Matemaatika Seltsi toimetised avaldatud paber milles ta tutvustas Ramsey numbreid. See töö ei puudutanud isegi graafikuid, vaid matemaatilise loogika probleemi. Ramsey tõestas, et väide, mis vastab teatud tingimustele, peab vähemalt osa ajast tõsi olema. Üks neist tingimustest seisnes selles, et väite testimiseks on olemas suur stsenaariumide "universum". Selle tulemuse saavutamisel näitas Ramsey, et Ramsey arv on lõplik.

Viis aastat hiljem näitasid Erdős ja Szekeres, et Ramsey arv k on väiksem kui 4^k. Ja 12 aastat pärast seda, Erdős näitas et see on suurem kui umbes $latex sqrt{2}^k$. Selleks arvutas ta välja tõenäosuse, et juhuslikult värvitud servadega graafik sisaldab monokromaatilist klikki. See "tõenäosuslik" tehnika sai graafiteoorias tohutult mõjuvõimsaks. Samuti jäi see lõksu R(k) kahe eksponentsiaalselt kasvava väravaposti vahel: $lateks sqrt{2}^k$ ja $lateks 4^k$.

Aastakümnete möödudes püüdsid paljud matemaatikud vähendada lõhet Ramsey arvu võimalike väärtuste vahel. Mõnel see õnnestus: 1975. aastal Joel Spencer kahekordistas alampiiri. Ja rida pabereid autorilt Conlon, Andrew Thomason ja Ashwin Sah surus ülemise piiri alla 4. aastaks umbes $lateksi 2^{log(k)^2020}$ võrra. Võrreldes Ramsey numbri piiride suurustega, olid need kohandused väikesed. Seevastu Erdősi ja Szekeresi valemis R(k) < 4^k oleks plahvatuslik paranemine, kasvades kiiresti kui k läheb suuremaks.

"See tundub lihtsalt armas väike küsimus," ütles Rob Morris, matemaatik Brasiilia puhta ja rakendusmatemaatika instituudis IMPA Rio de Janeiros, kes koostas uue tulemuse koos Campose, Griffithsi ja Sahasrabudhega. "Seda on veidi peen hinnata. Kuid inimesed hoolivad sellest väga." See on tõenäoliselt alahinnang. "Kui nad oleksid seda 1936. aastal tõestanud, oleksid inimesed öelnud: "OK, mis siis on?" ütles Béla Bollobás, kes oli Morrise ja Sahasrabudhe doktoriõppe nõunik Memphise ülikoolis. "Sellest ajast alates on tõestatud, et see on väga suur probleem, sest aastate jooksul on Ramsey probleemi erinevate variantide kohta kirjutatud mitu tuhat paberit." Nagu Liana YepremyanEmory ülikooli matemaatik ütles: "Ramsey numbrid loovad silla kombinatoorika ning tõenäosuse ja geomeetria vahel."

Mänguteooria

 2018. aasta augustis oli Sahasrabudhe Morrise järeldoktor IMPA-s. Nad lootsid alustada uut projekti Griffithsiga, kes õpetab lähedal asuvas paavstlikus katoliku ülikoolis. Conloni paber köitis nende tähelepanu. Dokumendis kirjeldati võimalikku strateegiat Ramsey numbri eksponentsiaalseks parandamiseks. Griffiths, Morris ja Sahasrabudhe hakkasid selle ideega mängima.

"Alguses oli see tõesti põnev," meenutas Sahasrabudhe. Ta ütles, et neil kulus vaid umbes kuu, et visandada oma argumendid.

Nende plaan oli tugineda ideedele, mida kasutati Erdősi ja Szekeresi algses tõestuses, et $lateks R(k) < 4^k$. Tõestamaks, et Ramsey arv on maksimaalselt $latex 4^k$, kujutage ette, et mängite mängu täielikul graafikul $lateksi 4^k$ sõlmedega. Mängus on kaks mängijat. Esiteks värvib vastane iga serva kas punaseks või siniseks, lootes värvida servad viisil, mis väldib monokromaatilise kliki teket. k sõlmed.

Kui vastane on värvimise lõpetanud, on teie ülesanne otsida monokromaatilist klikki. Kui leiate ühe, siis võidate.

Selle mängu võitmiseks võite järgida lihtsat strateegiat. See aitab (metafooriliselt) mõelda oma sõlmede kahte ämbrisse sorteerimisele. Ühe ämbri sõlmed moodustavad sinise kliki ja teise sõlmed punase kliki. Mõned sõlmed kustutatakse ja neist ei saa enam kunagi midagi kuulda. Alguses on mõlemad ämbrid tühjad ja iga sõlm on kandidaat kummassegi sisenemiseks.

Alustage mis tahes sõlmest, mis teile meeldib. Seejärel vaadake ühendusservi. Kui pooled või enam servadest on punased, kustutage kõik sinised servad ja sõlmed, millega need on ühendatud. Seejärel pange oma algne valik "punasesse" ämbrisse. Kõik selle sõlme punased servad on endiselt elus ja terved, klammerdudes ämbri seest ülejäänud graafiku külge. Kui üle poole servadest on sinised, kustutate analoogselt punased servad ja sõlmed ning paned sinisesse ämbrisse.

Korrake, kuni teil pole enam ühtegi sõlme. (Kuna graafik on valmis, on iga ülejäänud sõlm mis tahes punktis ühendatud mõlema ämbriga, kuni see asetatakse ühte neist.)

Kui olete lõpetanud, vaadake ämbrite sisse. Kuna sõlm läks punasesse ämbrisse alles pärast seda, kui tema sinised naabrid olid kõrvaldatud, on kõik punase ämbri sõlmed ühendatud punaste servadega - need moodustavad punase kliki. Samamoodi moodustab sinine ämber sinise kliki. Kui teie algsel graafikul on vähemalt $latex 4^k$ sõlme, on võimalik tõestada, et üks neist ämbritest peab sisaldama vähemalt k sõlmed, tagades algses graafikus monokromaatilise kliki.

See argument on nutikas ja elegantne, kuid see paneb teid looma kaks klikki – ühe sinise ja ühe punase – kuigi teil on tegelikult vaja ainult ühte. Tõhusam oleks alati punaseks minna, selgitas Conlon. Selle strateegia kohaselt valite igal sammul sõlme, kustutate selle sinised servad ja viskate selle punasesse ämbrisse. Punane ämber täitus siis kiiresti ja te koguneksite punase kliki k sõlmed poole ajaga.

Kuid teie strateegia peab töötama mis tahes punase-sinise värvingu puhul ja on raske teada, kas leiate alati sõlme, millel on palju punaseid servi. Seega on Conloni soovituse järgimisel oht sattuda sõlme, millel pole peaaegu ühtegi punast serva. See sunniks teid suure osa graafikust korraga kustutama, jättes teid vaevama oma klikki üles ehitada, enne kui sõlmed otsa saavad. Conloni soovituse elluviimiseks pidid Griffiths, Morris ja Sahasrabudhe tõestama, et see risk on välditav.

Avatud raamatu eksam

Oma mänguviisi värskendamisel järgisid Griffiths, Morris ja Sahasrabudhe veidi tiirlevat teed. Selle asemel, et luua monokromaatiline klikk otse, visates sõlmed nende punastesse ja sinistesse ämbritesse, keskendusid nad kõigepealt punaseks raamatuks nimetatava struktuuri ehitamisele.

Graafiteoorias koosneb raamat kahest osast: seal on monokromaatiline klikk, mida nimetatakse "selgrooks", ja teine, eraldiseisev sõlmede klaster, mida nimetatakse "lehtedeks". Punases raamatus on kõik lülisamba sõlme ühendavad servad punased, nagu ka servad, mis ühendavad selgroogu lehtedega. Lehtede sõlmpunkte ühendavad servad võivad aga olla mis tahes värvikombinatsioonid. Conlon oli oma 2018. aasta artiklis märkinud, et kui leiate raamatu lehtede seest punase kliki, võite selle kombineerida selgrooga, et saada suurem punane klikk. See võimaldab jagada suure punase kliki otsingu kaheks lihtsamaks otsinguks. Esiteks otsige üles punane raamat. Seejärel otsige raamatu lehekülgedelt klikki.

Griffiths, Morris ja Sahasrabudhe soovisid mängu võitnud algoritmi kohandada nii, et see ehitaks punase kliki asemel punase raamatu. Kuigi nad otsustasid selle plaaniga vaid mõne nädala pärast oma projekti, kulub selle toimimiseks aastaid. Neil oli siiski vaja vältida ohtu kaotada kõik oma punased servad.

"Olime väga pikka aega ummikus," ütles Campos, kes liitus projektiga 2021. aastal.

Tänavu jaanuaris nõustusid neli matemaatikut üle minema ülesande teisele versioonile. See versioon kõlab keerulisemalt, kuid osutus lihtsamaks.

Kogu aeg oli meeskond keskendunud Ramsey numbrile R (k), tuntud ka kui "diagonaalne" Ramsey number. Graafik suurusega R(k) peab sisaldama k sõlmed, mis kõik on ühendatud sama värvi servadega, kuid pole vahet, kas see värv on punane või sinine. Teisest küljest on "diagonaaliväline" Ramsey arv R(k, l) mõõdab, kui suur peab olema graafik, enne kui see sisaldab kas punast klikki koos k sõlmed või sinine klikk koos l sõlmed. Selle asemel, et jätkata diagonaali probleemiga tegelemist, otsustas rühm proovida diagonaalivälist versiooni. See osutus ilmutuslikuks.

"Pikka aega tundus, et iga uks, mille peale lükkasite, on kas poltidega kinni või vähemalt üsna raske läbi pääseda," ütles Griffiths. "Ja pärast seda muutust tundsite lihtsalt, et kõik uksed on avatud. Kuidagi tundus, et kõik töötab. Diagonaalivälises versioonis leidsid nad viisi, kuidas teatud protokolli järgides korraga kustutada hunnik siniseid servi, mis suurendas punaste servade tihedust ja viis diagonaalse Ramsey numbri paranemiseni. Seda meetodit, mida nimetatakse "tiheduse juurdekasvu" argumendiks, oli varem kasutatud lahendamiseks muud olulised probleemid kombinatoorikas, kuid seda ei kasutatud Ramsey numbriprobleemi lahendamisel.

Neli matemaatikut kasutasid seejärel diagonaalist väljas oleva Ramsey numbri uut piirangut, et vabastada tee diagonaali tulemusele. Veebruari alguseks olid nad lõpuks alandanud Ramsey arvu piiri eksponentsiaalse teguri võrra – matemaatikud olid seda saavutust taotlenud peaaegu sajandi. Ja nad tegid seda, moderniseerides sama argumentatsiooni, mille Erdős ja Szekeres olid esitanud 1935. aastal.

Epsilon, Epsilon

Pärast 16. märtsi kõnelusi hakkasid kohalviibijad kuulujutte kinnitama. Fotod Sahasrabudhe jutust levisid telefonikõnede ja privaatsõnumite kaudu — isegi a ebamäärane, kuid sugestiivne postitus matemaatik Gil Kalai ajaveebis. Campos, Griffiths, Sahasrabudhe ja Morris väitsid, et on näidanud, et $lateksi R(k) < 3.993^k$. Sel õhtul neli autorit postitas oma paberi internetti, mis võimaldab matemaatikutel uut tõestust ise näha.

"Ma arvan, et paljud meist ei oodanud oma elu jooksul sellist paranemist sisuliselt," ütles Matija Bucić, Princetoni ülikooli ja edasijõudnute uuringute instituudi matemaatik. "Ma arvan, et see on täiesti hämmastav tulemus."

Paljud eksperdid loodavad, et pärast eksponentsiaalse barjääri langetamist järgneb kiiresti rohkem edusamme. Uue artikli autorid ei ajanud oma meetodit tahtlikult oma piiridesse, et vältida oma argumendi hägustumist tarbetute detailidega. "Olen väga huvitatud sellest, kui kaugele see meetod tegelikult ulatub, sest mul pole õrna aimugi," ütles Campos.

"See on täiesti geniaalne, täiesti imeline tõestus ja tõeline läbimurre. Nii et nüüd ma ootan, et uluväravad avatakse," ütles Bollobás. „Olen ​​veendunud, et kolme aasta pärast on arutelu võimalike parenduste üle. Kas saame 3.993 parandada 3.9-le? Võib-olla kuni 3.4? Ja kuidas on 3-ga?"

Uus tõend on 56 lehekülge ja võtab nädalaid, enne kui kombinatoorika kogukond iga detaili täielikult kontrollib. Kuid kolleegid on optimistlikud. "See grupp autoreid, nad on väga tõsised inimesed. Ja nad on inimesed, kes on väga-väga head väga tehnilistes asjades, ”ütles Wigderson.

Kui rääkida tema kaastöötajatest, nõustub Griffiths. “See on privileeg töötada koos säravate inimestega, kas pole? Ja ma arvan, et tunnen selle eest väga tänulikkust,” sõnas ta. "Kui nad oleksid selle minu hooleks jätnud, oleksin võib-olla võtnud veel viis aastat, et üksikasjad paika saada."