Matematiker upptäcker nytt sätt att förutsäga struktur i grafer | Quanta Magazine

Det har varit ett spännande år inom kombinatorisk forskning. I början av 2023 blev matematiker chockade när två av d största problemen i fält löstes på lika många månader. Nu har en tredje stor fråga fallit med ett 14-sidigt bevis "som har absolut alla rätta idéer", sa Mehtaab Sawhney från Massachusetts Institute of Technology, som tillade: "Det är helt chockerande."

Den frågan handlar om så kallade Ramsey-tal – fundamentala storheter som återspeglar gränserna för möjlig oordning. Dessa siffror mäter storleken som samlingar av hörn och kanter, kallade grafer, kan uppnå innan de oundvikligen ger upphov till mönster och struktur.

Matematiker har studerat Ramsey-tal, som är notoriskt svåra att fastställa, i nästan ett sekel. Genom att göra det har de utvecklat tekniker som har lett till framsteg inom en mängd olika discipliner bortom grafteori, inklusive talteori och kryptografi.

Men det nya beviset, publicerades på nätet tidigare denna månad, markerar ett avsteg från dessa tekniker. Den löser inte bara ett problem som har motstått framsteg i mer än 40 år, utan presenterar också en ny färdplan för hur matematiker kan tackla Ramsey-problem framöver.

Festplanering möter grafteori

För att förstå vad ett Ramsey-nummer är, föreställ dig att du är värd för en fest.

Hur många personer skulle du behöva bjuda in för att garantera att det kommer att finnas en grupp människor som alla känner varandra, eller en grupp som alla är främlingar? Du kan koda denna fråga på grafernas språk. Tilldela en vertex till varje person. För n människor, du får n hörn. Förbind varje par av hörn med en kant. Färga kanten röd om personerna i fråga känner varandra, och blå om de är främlingar.

En grupp gemensamma bekanta eller främlingar representeras av en struktur som kallas en klick: en uppsättning hörn sammankopplade med kanter av samma färg. Ramsey-numret r(s, t) är det minsta antal personer du måste bjuda in för att göra det omöjligt att undvika att inkludera en grupp med s bekanta eller t främlingar — på grafteorins språk, en röd klick av storlek s eller en blå klick av storlek t.

Det vet vi till exempel r(4, 5) = 25. Du kan alltså vara värd för en fest med 24 personer, av vilka några känner varandra, utan att inkludera en grupp på fyra gemensamma bekanta eller fem främlingar. Men lägg till en person till så kan du inte undvika att skapa minst en av dessa strukturer.

Ett av årets tidigare genombrott inom kombinatorik gav en snävare övre gräns för "symmetriska" Ramsey-tal, där de röda och blå klicken är lika stora. Med asymmetriska Ramsey-tal – ämnet för det nya resultatet – fixar matematiker storleken på den röda klicken och frågar vad som händer när storleken på den blå klicken blir godtyckligt stor.

Matematiker har bara kunnat beräkna exakt en handfull av de minsta Ramsey-talen. Det bevisade de r(4, 5) = 25 år 1995. Men ingen vet värdet av r(4, 6). På samma sätt, i början av 1980-talet, de visade den där r(3, 9) = 36, men r(3, 10) förblir ett öppet problem. (Det symmetriska fallet är lika svårt: r(4) = 18, men värdet av r(5) är inte känt.)

Och så matematiker försöker istället uppskatta Ramsey-tal – komma upp med övre och nedre gränser för deras värden.

På 1990-talet använde de tekniker för att slumpmässigt generera grafer för att bevisa att om den röda klicken är fixerad till 3, och den blå blir större och större, växer storleken på Ramsey-talet med kvadraten på storleken på den blå klicken. Med andra ord, r(3, t) är approximativt t².

Det nya beviset frågar vad som händer när storleken på den röda klicken sätts till 4, snarare än 3. På 1930-talet slogs det fast att r(4, t) växer inte snabbare än runt t³. Men den bästa nedre gränsen, som hittades på 1970-talet, handlar om t^5/2 — betydligt mindre.

Ansträngningar att stänga gapet genom att höja den nedre gränsen eller sänka den övre misslyckades i årtionden, tills ett par matematiker lade till en nyckelingrediens.

Dold i vanlig syn

2019, Sam Mattheus, då en doktorand vid Free University of Brussels (VUB) letade efter inspiration. Hans expertis var i finit geometri, studiet av arrangemang av punkter, linjer och andra strukturer i speciellt definierade utrymmen. Men även om han tyckte att arbetet var intressant kände han sig begränsad av hur strikta och exakta dessa geometriska konstruktioner måste vara.

Sedan såg han ett papper av två matematiker, Dhruv Mubayi från University of Illinois, Chicago och Jacques Verstraete vid University of California, San Diego. De tänkte om hur de skulle närma sig Ramsey-problem. Medan traditionella tekniker innebär att slumpmässigt generera grafer för att få bra uppskattningar av Ramsey-tal, började Mubayi och Verstraete med "pseudoslumpmässiga" konstruktioner som ser slumpmässiga ut, men som inte är det.

Något klickade i Mattheus. Kanske, tänkte han, kunde hans geometriska perspektiv hjälpa. Under de kommande åren, medan han avslutade sitt examensarbete, höll han denna idé i bakhuvudet. Han ansökte sedan om ett Fulbright-stipendium, vilket skulle göra det möjligt för honom att fortsätta en postdoc med Verstraete i USA

2022, kort efter att Mattheus tilldelades Fulbright (tillsammans med en annan gemenskap), flyttade han till UCSD och började arbeta med Verstraete på r(4,t). Matematikerna ville höja den nedre gränsen för att möta den kända övre gränsen. För att göra det måste de hitta en graf med nästan t³ hörn som inte hade några röda klickar av storlek 4 eller blå klickar av storlek t.

För att få sina bevis att fungera omformulerade de problemet. Föreställ dig att helt enkelt ta bort varje blå kant. Målet blir nu att hitta en graf utan röda klick i storlek 4 och inga oberoende uppsättningar av storlek t (det vill säga uppsättningar av t hörn utan kanter).

Mubayi och Verstraetes arbete 2019 antydde att om du kan konstruera en pseudoslumpmässig graf utan röda klick av storlek 4, så kan du ta slumpmässiga bitar av den för att få mindre grafer utan några stora oberoende uppsättningar. Detta var precis vad Mattheus och Verstraete ville hitta. Genom att börja med en ännu större graf hoppades de hitta en graf med nästan t³ hörn som uppfyllde deras kriterier. "Inuti dessa grafer döljer sig bättre Ramsey-grafer," sa Verstraete.

Problemet var att komma på rätt pseudoslumpmässig konstruktion till att börja med.

Matematikerna var tvungna att ta sig dit på ett något cirkulerande sätt. De började inte med en pseudoslumpmässig graf. De började inte med en graf alls.

Istället kom Mattheus ihåg ett konstigt föremål som kallas en hermitisk enhet, något som ändliga geometrar tenderar att vara mycket bekanta med - men som en matematiker som arbetar i kombinatorik var osannolikt att någonsin stöta på.

En hermitisk enhet är en speciell uppsättning punkter på en kurva, tillsammans med linjer som passerar genom dessa punkter i specifika konfigurationer. Avgörande är att den också kan representeras som en graf som består av många stora men knappt överlappande klick.

Denna graf är välkänd och många av dess egenskaper har studerats. Men det hade aldrig övervägts i samband med Ramsey-problem. "Det är mycket specifikt för den här affären med ändlig geometri," sa Mattheus.

Grafen kanske inte verkar användbar vid första anblicken, eftersom den innehåller så många stora klick. Men en nyckelfunktion hos den hermitiska unitalen är att den bara innehåller storlek-4 klicker vars hörn är samlade på ett atypiskt sätt. På grund av denna egenskap var det relativt lätt för matematikerna att förstöra dessa oönskade klick genom att radera kanter slumpmässigt.

Dessa raderingar gav dem en ny graf utan storlek 4-klickar - men den innehöll fortfarande stora oberoende uppsättningar. Mattheus och Verstraete behövde nu bevisa att denna graf var pseudoslumpmässig. Genom att göra det kunde de äntligen använda 2019 års bevis som de hade hoppats. De tog slumpmässiga subgrafer med ca t³ hörn och kunde garantera att dessa subgrafer var fria från oberoende uppsättningar av storlek t.

Detta fullbordade beviset. "Den här konstruktionen är absolut vacker," sa Sawhney.

Verket förebådar ett skifte i hur matematiker tänker kring Ramsey-problem. "Det är väldigt, väldigt naturligt att försöka använda slumpmässighet för att försöka driva igenom saker och få en så bra gräns som möjligt," sa David Conlon vid California Institute of Technology. "Men vad detta verkligen visar är att slumpmässighet bara tar dig så långt."