Ett mycket stort litet språng framåt i grafteori

Den 15 mars skickade spännande seminariemeddelanden mullrande genom kombinatorikområdet, den matematiska studien av räkning. Tre samarbetspartners planerade att hålla samordnade samtal följande dag. Julian Sahasrabudhe skulle tilltala matematiker i Cambridge, England, medan Simon Griffiths skulle dela nyheterna i Rio de Janeiro och Marcelo Campos i São Paulo. Alla tre föredragen hade identiska titlar och kryptiska sammanfattningar med två meningar som hänvisade till "den senaste tidens framsteg i ett gammalt problem med Erdős." Medan Paul Erdős, en ungersk matematiker som dog 1996, poserade hundratals problem under hans karriär spånade kombinatorerna snabbt den specifika fråga som trion planerade att prata om. Rykten snurrade om något som kallas Ramsey-talet, en av de svåraste kvantiteterna att beräkna i all matematik.

Ramsey-siffror har skapat en hel disciplin som kallas Ramsey-teori, som letar efter oundvikliga mönster i ett stort antal system.

Säg till exempel att du försöker sprida alla heltal mellan ett antal hinkar och att du vill undvika att placera sekvenser av jämnt fördelade tal i någon av hinkarna. Ramseys teori visar att du kommer att misslyckas (om du inte har oändligt många hinkar). Teorin kan appliceras på det mesta du kan räkna. Dess centrala lärdom är att "du kan inte skapa ett helt kaotiskt system", säger Benny Sudakov, matematiker vid det schweiziska federala tekniska institutet i Zürich.

Ramsey-talet kvantifierar hur stort ett paradigmatiskt exempel måste vara innan särskilda mönster oundvikligen uppstår. Men trots dess centralitet har ingen kunnat beräkna Ramsey-talet för alla utom enklaste fall. Det bästa de har kunnat göra är att hitta gränser (eller gränser) för vad det kan vara. Redan då hade den övre gränsen som först etablerades av Erdős och en medarbetare för nästan ett sekel sedan knappt visats.

Sedan, i seminarierna den 15 mars, och i en tidning som publicerades senare samma kväll, meddelade forskarna att de hade förbättrat den övre gränsen för Ramsey-talet med ett exponentiellt belopp.

"Jag var golvad", sa Yuval Wigderson, en matematiker vid Tel Aviv University, på att höra om det nya resultatet. "Jag skakade bokstavligen i en halvtimme till en timme."

Partilinjerna

Ramsey-teorin ställer oftast frågor antingen om heltal eller om grafer. En graf, i detta sammanhang, hänvisar till samlingar av punkter som kallas noder, förbundna med linjer som kallas kanter, som kan ha egenskaper som längd eller - som i fallet med Ramsey-talen - färg.

En komplett graf är både komplicerad och enkel - varje nod är kopplad till varannan nod. Ramsey-numret beskriver hur många noder en komplett graf måste innehålla för att tvingas ha en viss struktur. Säg att kanterna på en komplett graf tilldelas en av två färger: röd eller blå. Och säg att du försöker färglägga kanterna på ett sätt som undviker att koppla ihop en grupp av noder med kanter av samma färg. 1930 bevisade Frank Ramsey att om en graf är tillräckligt stor blir det omöjligt att undvika att skapa vad matematiker kallar en monokromatisk klick - en grupp av noder vars gemensamma kanter är antingen helt röda eller helt blå.

Hur stor, exakt, måste en graf vara innan en monokromatisk klick tvingas dyka upp? Svaret beror på klickens storlek. Ramsey visade att det finns ett nummer, nu kallat Ramsey-numret, som representerar det minsta antalet noder för vilka en monokromatisk klick av en given storlek måste existera, oavsett hur kanterna är färgade.

Men storleken på Ramsey-numret är svår att fastställa. 1935, fem år efter att Ramsey visade att den existerade, gav Erdős och George Szekeres en ny, snävare övre gräns för hur stort Ramsey-numret är för en klick av en given storlek. Men sedan dess har matematiker knappt kunnat förbättra Erdős och Szekeres beräkningar.

För att få en bättre intuition för vad detta betyder, överväg ett klassiskt exempel, där noder representerar gäster på en fest. Färga kanten mellan två gäster röd om de har träffats tidigare och blå om de inte har det. Du kan välja vilken klickstorlek du vill – bjud in tillräckligt många till festen, och du kan inte undvika att antingen bjuda in en grupp människor som alla känner varandra (en klick i flera betydelser av ordet) eller att bjuda in en grupp människor som har aldrig träffats förut.

"Det enklaste du kan ha i en graf är en monokromatisk klick," sa Maria Chudnovsky, en matematiker vid Princeton University. "Det är ganska häpnadsväckande att i varje enorm graf kan du hitta en stor av dem. Det är helt oklart.”

De första Ramsey-talen är relativt enkla att beräkna. Låt oss säga att du vill veta storleken på den minsta grafen som oundvikligen måste hålla en klick av storlek två, eller R(2) för matematiker. Eftersom en komplett graf med två noder bara är två noder förbundna med en kant, och den kanten måste vara antingen röd eller blå, är R(2) 2. Mer allmänt, R(k), eller Ramsey-numret för k, är det minsta antalet noder utöver vilket en graf inte kan undvika att innehålla en klick av storlek k.

Det är inte så svårt att visa att Ramsey-talet för en klick i storlek 3, eller R(3), är 6 (se bilden). Men det var inte förrän 1955 som R(4) sattes fast vid 18. R(5) är fortfarande okänd - det är minst 43 och inte större än 48. Även om dessa siffror är små, går det inte att sålla igenom alla möjliga färger av frågan, sade David Conlon från California Institute of Technology. Tänk på antalet färger på en komplett graf med 43 noder. "Du har 903 kanter; var och en av dessa kan färgas på två sätt”, förklarade han. "Så du får 2⁹⁰³, som bara är astronomiskt stort."

När storleken på klicken ökar blir uppgiften att spika Ramsey-numret bara svårare. Erdős sa att ett fullständigt krig med matematiskt krävande utomjordingar skulle vara lättare än att försöka räkna ut R(6), vilket är någonstans mellan 102 och 165. Osäkerhetsintervallet växer snabbt: Enl. uppskattningar sammanställda av Stanisław Radziszowski, R(10) kan vara så liten som 798 och så stor som 23,556 10. Men matematikernas mål når långt bortom Ramsey-talet XNUMX. De vill ha en formel som ger en bra uppskattning av R(k), även — eller särskilt — när k är extremt stor.

"Jag vet inte om en person inom kombinatorik som inte har tänkt på det här problemet åtminstone lite," sa Wigderson. "Det här problemet är, tror jag, väldigt speciellt."

Ordning i domstolen

Frank Ramsey var en eklektisk, lysande figur som dog när han var 26 år gammal. Bara veckor innan han dog Proceedings of the London Mathematical Society publicerade pappret där han introducerade Ramsey-nummer. Det arbetet handlade inte ens om grafer, utan om ett problem inom matematisk logik. Ramsey bevisade att ett uttalande som uppfyller vissa villkor måste vara sant åtminstone en del av tiden. Ett av dessa villkor var att det finns ett stort "universum" av scenarier att testa påståendet i. Som en språngbräda till detta resultat visade Ramsey att Ramsey-talet är ändligt.

Fem år senare visade Erdős och Szekeres att Ramsey antalet k är mindre än 4^k. Och 12 år efter det, Erdős visade att den är större än ungefär $latex sqrt{2}^k$. För att göra det beräknade han chanserna att en graf med slumpmässigt färgade kanter innehåller en monokromatisk klick. Denna "probabilistiska" teknik blev enormt inflytelserik inom grafteorin. Det fångade också R(k) mellan två exponentiellt växande målstolpar: $latex sqrt{2}^k$ och $latex 4^k$.

När decennierna gled förbi försökte många matematiker att minska klyftan mellan de möjliga värdena för Ramsey-talet. Några lyckades: 1975 Joel Spencer fördubblat den nedre gränsen. Och en serie tidningar av Conlon, Andrew Thomason och Ashwin Sah tryckt ned den övre gränsen med en faktor på cirka $latex 4^{log(k)^2}$ år 2020. Men jämfört med storleken på ramsey-numrets gränser var dessa justeringar små. Däremot kan varje minskning till 4:an i Erdős och Szekeres formel R(k) < 4^k skulle vara en exponentiell förbättring, växa snabbt som k blir större.

"Det verkar bara vara en söt liten fråga," sa Rob Morris, en matematiker vid IMPA, Brasiliens institut för ren och tillämpad matematik, i Rio de Janeiro, som skrev det nya resultatet tillsammans med Campos, Griffiths och Sahasrabudhe. "Det är lite subtilt att uppskatta. Men folk bryr sig verkligen om det." Detta är möjligen en underdrift. "Hade de bevisat det 1936, skulle folk ha sagt, okej, så vad är grejen?" sa Béla Bollobás, som var Morris och Sahasrabudhes doktorandrådgivare vid University of Memphis. "Sedan dess har det bevisats att det är ett mycket stort problem, för under åren har flera tusen artiklar skrivits om olika varianter av Ramsey-problemet." Som Liana Yepremyan, en matematiker vid Emory University, sa: "Ramsey-talen skapar den bryggan mellan kombinatorik och sannolikhet och geometri."

Spel teori

 I augusti 2018 var Sahasrabudhe postdoktor under Morris vid IMPA. De två hoppades kunna starta ett nytt projekt med Griffiths, som undervisar vid det närliggande påvliga katolska universitetet, när en tidning av Conlon fångade deras uppmärksamhet. Tidningen beskrev en möjlig strategi för att få en exponentiell förbättring av Ramsey-talet. Griffiths, Morris och Sahasrabudhe började leka med idén.

"Det var riktigt spännande i början," mindes Sahasrabudhe. Det tog dem bara ungefär en månad, sa han, att lägga ut en skiss av deras argument.

Deras plan var att bygga på idéer som användes i Erdős och Szekeres ursprungliga bevis på att $latex R(k) < 4^k$. För att bevisa att Ramsey-talet är högst $latex 4^k$, tänk dig att spela ett spel på en komplett graf med $latex 4^k$ noder. Spelet har två spelare. Först färgar din motståndare varje kant antingen röd eller blå, i hopp om att färga kanterna på ett sätt som undviker att skapa en monokromatisk klick av k knutpunkter.

När din motståndare är klar med färgläggning är det ditt jobb att söka efter en monokromatisk klick. Hittar du en så vinner du.

För att vinna det här spelet kan du följa en enkel strategi. Det hjälper att tänka (metaforiskt) på att sortera dina noder i två hinkar. Noderna i en hink kommer att bilda en blå klick, och noderna i den andra kommer att bilda en röd klick. Vissa noder kommer att raderas, för att aldrig höras från igen. I början är båda hinkarna tomma, och varje nod är en kandidat för att gå in i endera.

Börja med vilken nod som helst som du gillar. Titta sedan på anslutningskanterna. Om hälften eller fler av kanterna är röda, ta bort alla blå kanter och noderna de är anslutna till. Lägg sedan ditt ursprungliga val i den "röda" hinken. Alla den här nodens röda kanter lever fortfarande och har det bra och klamrar sig fast på resten av grafen från insidan av hinken. Om mer än hälften av kanterna är blå, raderar du analogt de röda kanterna och noderna och lägger dem i den blå hinken.

Upprepa tills du inte har några noder kvar. (Eftersom grafen är klar är varje återstående nod vid vilken punkt som helst kopplad till båda hinkarna tills den placeras i en av dem.)

När du är klar, titta in i hinkarna. Eftersom en nod gick in i den röda hinken först efter att dess blå grannar eliminerats, är alla noder i den röda hinken sammankopplade med röda kanter - de bildar en röd klick. Likaså bildar den blå hinken en blå klick. Om din ursprungliga graf har minst $latex 4^k$ noder, är det möjligt att bevisa att en av dessa hinkar måste innehålla minst k noder, vilket garanterar en monokromatisk klick i den ursprungliga grafen.

Detta argument är smart och elegant, men det får dig att bygga två klick - en blå och en röd - även om du egentligen bara behöver en. Det skulle vara mer effektivt att alltid gå rött, förklarade Conlon. Under denna strategi skulle du välja en nod vid varje steg, radera dess blå kanter och kasta den i den röda hinken. Den röda hinken skulle då snabbt fyllas, och du skulle samla en röd klick av k noder på halva tiden.

Men din strategi måste fungera för vilken röd-blå färg som helst, och det är svårt att veta om du alltid kan hitta en nod med många röda kanter. Så att följa Conlons förslag riskerar att stöta på en nod som nästan inte har några röda kanter fästa vid den. Det skulle tvinga dig att radera en stor del av grafen på en gång, vilket gör att du behöver kämpa för att bygga din klick innan du får slut på noder. För att genomföra Conlons förslag behövde Griffiths, Morris och Sahasrabudhe bevisa att denna risk gick att undvika.

Ett prov i öppen bok

När Griffiths, Morris och Sahasrabudhe uppdaterade sitt spelande följde de en något mer omständlig väg. Istället för att bygga en monokromatisk klick direkt genom att kasta noder i sina röda och blå hinkar, fokuserade de först på att bygga en struktur som kallas en röd bok.

En bok, i grafteori, består av två delar: Det finns en monokromatisk klick, kallad "ryggraden", och en andra, distinkt kluster av noder som kallas "sidorna". I en röd bok är alla kanter som förbinder noder inom ryggraden röda, liksom kanterna som länkar ryggraden till sidorna. Kanterna som förbinder noderna på sidorna kan dock vara vilken kombination av färger som helst. Conlon hade noterat i sin tidning från 2018 att om du kan hitta en röd klick på sidorna i en bok, så kan du kombinera den med ryggraden för att få en större röd klick. Detta låter dig bryta upp en sökning efter en stor röd klick i två enklare sökningar. Leta först efter en röd bok. Leta sedan efter en klick på sidorna i boken.

Griffiths, Morris och Sahasrabudhe ville justera den spelvinnande algoritmen så att den byggde en röd bok istället för en röd klick. Även om de bestämde sig för denna plan bara några veckor in i sitt projekt, skulle det ta år att få det att fungera. De behövde fortfarande avvärja hotet att förlora alla sina röda kanter.

"Vi var fast väldigt länge," sa Campos, som gick med i projektet 2021.

I januari kom de fyra matematikerna överens om att byta till en annan version av problemet. Den versionen låter mer komplicerad, men det visade sig vara lättare.

Hela tiden hade laget varit fokuserat på Ramsey-numret R(k), även känt som det "diagonala" Ramsey-numret. En graf av storlek R(k) måste innehålla k noder, alla förbundna med kanter av samma färg, men det spelar ingen roll om den färgen är röd eller blå. Å andra sidan, det "off-diagonala" Ramsey-numret R(k, l) mäter hur stor en graf måste vara innan den innehåller antingen en röd klick med k noder, eller en blå klick med l knutpunkter. Istället för att fortsätta hacka på diagonalproblemet bestämde sig gruppen för att prova den off-diagonala versionen. Detta visade sig vara avslöjande.

"Under lång tid kändes det som att varje dörr du tryckte på antingen var stängd med bultar eller åtminstone ganska svår att ta sig igenom," sa Griffiths. "Och efter den förändringen kändes det som att varje dörr var öppen. På något sätt verkade allt bara fungera.” I den off-diagonala versionen hittade de ett sätt att ta bort ett gäng blå kanter på en gång efter ett visst protokoll, vilket ökade tätheten av röda kanter och ledde till en förbättrad gräns för det off-diagonala Ramsey-numret. Denna metod, kallad "density increment"-argument, hade tidigare använts för att lösa andra viktiga problem inom kombinatorik, men det hade inte använts på Ramsey-nummerproblemet.

De fyra matematikerna använde sedan den nya gränsen på det off-diagonala Ramsey-numret för att bana väg för det diagonala resultatet. I början av februari hade de äntligen sänkt gränsen för Ramsey-talet med en exponentiell faktor, en prestation som matematiker hade eftersträvat i nästan ett sekel. Och de gjorde det genom att modernisera samma argumentation som Erdős och Szekeres hade lagt fram 1935.

Epsilon, Epsilon

Efter samtalen den 16 mars började deltagarna bekräfta ryktena. Foton från Sahasrabudhes tal cirkulerade genom telefonsamtal och privata meddelanden – även i en vagt men suggestivt inlägg på matematikern Gil Kalais blogg. Campos, Griffiths, Sahasrabudhe och Morris påstod sig ha visat att $latex R(k) < 3.993^k$. Den natten, de fyra författarna lade ut sin tidning på nätet, så att matematiker kan se det nya beviset själva.

"Jag tror att många av oss inte förväntade oss att se en sådan förbättring under vår livstid, i huvudsak," sa Matija Bucić, en matematiker vid Princeton University och Institute for Advanced Study. "Jag tycker att det är ett helt fantastiskt resultat."

Många experter är hoppfulla om att fler framsteg snabbt kommer att följa med den exponentiella barriären avverkad. Författarna till den nya uppsatsen drev inte avsiktligt sin metod till dess gränser, för att undvika att deras argument fördunklas med onödiga detaljer. "Jag är väldigt intresserad av hur långt metoden faktiskt kan gå, för jag har ingen aning," sa Campos.

"Det är ett helt genialt, helt underbart bevis och ett genuint genombrott. Så nu förväntar jag mig att dammluckorna öppnas”, sa Bollobás. – Jag är övertygad om att om tre år kommer debatten att handla om möjliga förbättringar. Kan vi förbättra 3.993 till 3.9? Kanske till 3.4? Och vad sägs om 3?"

Det nya beviset kommer in på 56 sidor, och det kommer att ta veckor för varje detalj att vara helt verifierad av kombinatorikgemenskapen. Men kollegorna är optimistiska. "Den här gruppen av författare, de är väldigt seriösa människor. Och de är människor som är riktigt, riktigt bra på mycket tekniska saker, säger Wigderson.

När det kommer till hans medarbetare håller Griffiths med. ”Det är ett privilegium att få arbeta med briljanta människor, eller hur? Och jag tror att det är det jag känner mig väldigt tacksam för, säger han. "Om de hade lämnat det till mig hade jag kanske tagit fem år till för att få detaljerna rätt."