En närbild avslöjar "smältpunkten" för en oändlig graf | Quanta Magazine

2008 dog matematikern Oded Schramm i en vandringsolycka i Cascade-bergen cirka 50 mil öster om Seattle. Även om han bara var 46 år gammal, hade han konstruerat helt nya områden inom matematiken.

"Han var en fantastisk matematiker," sa Itai Benjamini, en matematiker vid Weizmann Institute of Science och Schramms vän och medarbetare. "Extremt kreativt, extremt elegant, extremt originellt."

Frågorna han ställde tänjer fortfarande på gränserna för sannolikhetsteori och statistisk fysik. Många av dessa frågor rör matematiska strukturer som har en fasövergång - en plötslig makroskopisk förändring, som att is smälter till vatten. Precis som olika material har olika smältpunkter, varierar också fasövergångar av matematiska strukturer.

Schramm antog att fasövergången i en process som kallas perkolation kan uppskattas genom att endast använda en närbild av systemet - kallat det lokala perspektivet - för många viktiga matematiska strukturer. Att zooma ut hela vägen och titta på det hela kommer inte att förändra beräkningen nämnvärt. Under de senaste 15 åren har matematiker slängt iväg små bitar av gissningarna, men hittills har de inte kunnat lösa det helt.

I en förtryck publicerat i oktober, Tom Hutchcroft vid California Institute of Technology och hans doktorand Philip Easo bevisade Schramms lokalitetsförmodan. Deras bevis bygger på stora idéer från sannolikhetsteori och andra matematikområden, som de kombinerade på ett smart sätt.

"Det är en anmärkningsvärd tidning. Det är en ansamling av långt arbete, sa Benjamini.

Oändliga kluster

Ordet "perkolering" syftade ursprungligen på vätskans rörelse genom ett poröst medium, såsom vatten som rinner genom kaffesump eller olja som sipprar genom sprickor i en sten.

1957 utvecklade matematikerna Simon Ralph Broadbent och John Michael Hammersley en matematisk modell av denna fysiska process. Under decennierna sedan har denna modell blivit ett studieobjekt i sin egen rätt. Matematiker studerar perkolation eftersom det gör en viktig balans: Installationen är enkel, men den uppvisar komplexa och förbryllande egenskaper.

"Det är en slags kanonisk modell för matematiker," sa Hutchcroft. "Du kan tänka på saker visuellt. Det gör det riktigt trevligt att jobba med.”

Perkolering börjar med en graf, som är en samling av hörn (punkter) som kan kopplas samman med kanter (linjer). Ett av de enklaste exemplen är ett kvadratiskt rutnät, med hörn uppradade för att bilda hörnen på rutor och kanter som förbinder några av dem.

Strax före sin död antog Schramm att Grimmett och Marstrands sats kunde generaliseras. Han trodde att perkolationströskeln helt och hållet bestäms av närbildsperspektivet, eller det "mikroskopiska" perspektivet för en stor klass av grafer som kallas transitiva grafer.

2009, Benjamini, Asaf Nachmias och Yuval Peres visat Schramms lokalitetsförmodan, som den nu är känd, för en specifik typ av transitiv graf som liknar ett träd. Schramm hade dock postulerat att det skulle gälla för alla transitiva grafer (med undantag för endimensionella grafer).

I en transitiv graf ser alla hörn likadana ut. Ett tvådimensionellt rutnät är ett exempel. Om du väljer vilka två hörn som helst, kan du alltid hitta en symmetri som flyttar en vertex till den andra.

Detta förhållande gäller för alla transitiva grafer. På grund av dessa symmetrier kommer de att se likadana ut om du zoomar in och tittar på två lika stora fläckar i en transitiv graf. Av denna anledning ansåg Schramm att närbildsperspektivet var tillräckligt för att matematiker skulle kunna beräkna perkolationströskeln för alla transitiva grafer.

Transitiva grafer kan ta många former och former. De kan vara ett enkelt rutnät, som består av kvadrater, trianglar, hexagoner eller någon annan form. Eller de kan bilda ett mer komplext objekt, som ett "3-regelbundet träd", där en central punkt ansluter till tre hörn, och varje vertex sedan förgrenar sig för att skapa två nya i oändlighet, vars första steg kan ses här:

Mångfalden av transitiva grafer bidrog till svårigheten att bevisa Schramms lokalitetsförmodan. Under de 15 åren mellan Schramms gissningar och Easo och Hutchcrofts bevis, bevisade olika grupper av matematiker gissningarna för specifika typer av grafer, men deras idéer sträckte sig aldrig till det allmänna fallet.

"Utrymmet för alla möjliga geometrier är bara så stort, och det finns alltid konstiga saker som lurar," sa Hutchcroft.

Bredda linsen

Easo och Hutchcroft letade initialt inte efter en lösning på Schramms lokalitetsförmodan, som gäller för oändliga grafer. De studerade istället perkolation på finita grafer. Men de hade en idé som plötsligt flyttade deras uppmärksamhet till gissningarna.

"Vi kom på det här nya verktyget och vi tänkte, åh, det här verkar vara en sådan sak som kan vara till hjälp för att attackera lokalitet," sa Easo.

För att bevisa gissningen behövde de visa att det mikroskopiska perspektivet ger en exakt ögonblicksbild av perkolationströskeln. När du bara tittar på en del av en graf och observerar ett stort anslutet kluster, kan du anta att grafen har ett oändligt kluster och därför ligger över perkolationströskeln. Easo och Hutchcroft gav sig i kast med att bevisa det.

De förlitade sig på en teknik som kan ses som att "vidga linsen". Börja vid en enda vertex. Zooma sedan ut för att se alla hörn som är bara en kant bort på den ursprungliga grafen. På det kvadratiska rutnätet kommer du nu att kunna se fem totala hörn. Vidga linsen igen för att se alla hörn inom ett avstånd av två kanter, och sedan ett avstånd på tre kanter, fyra kanter och så vidare.

Easo och Hutchcroft ställer in ratten som bestämmer hur många länkar det finns nära där de såg ett stort kluster. De vidgade sedan linsen och såg fler och fler kanter samlas i deras stora kluster. När de gjorde det var de tvungna att öka sannolikheten för att länkar skulle finnas, vilket gör det lättare att visa att grafen har en stor sammankopplad komponent. Detta är en delikat balansgång. De behövde bredda synfältet tillräckligt snabbt och lägga till länkar långsamt nog för att avslöja hela den oändliga grafen utan att dramatiskt ändra urtavlans position.

De kunde visa att stora kluster växer snabbare än mindre, så att, som Easo uttryckte det, "ditt kluster växer snabbare och snabbare när det blir större och större, precis som när du rullar en snöboll."

För det kvadratiska rutnätet växer vertexantalet relativt långsamt. Det är ungefär bredden på din lins i kvadrat. Efter 10 steg hittar du cirka 100 hörn. Men ett 3-regelbundet träd växer exponentiellt snabbare - ungefär 2 upphöjt till styrkan av din linsbredd. Efter 10 steg kommer du att se cirka 1,024 3 hörn. Illustrationen nedan visar hur det XNUMX-regelbundna trädet är mycket större efter bara sju steg, även om det kvadratiska rutnätet har fler hörn till en början. I allmänhet kan grafer ha olika tillväxthastigheter på olika skalor - de kan börja snabbt och sedan sakta ner.

Tillbaka 2018, Hutchcroft använde en liknande idé för att bevisa lokalitetsförmodan för snabbväxande grafer som det 3-regelbundna trädet. Men det fungerade inte för grafer med långsam tillväxt som det kvadratiska rutnätet, eller för grafer som växer med medelhastighet och uppfyller varken de matematiska kriterierna för snabb tillväxt eller de för långsam tillväxt.

"Det är här det blir riktigt frustrerande i tre år," sa Hutchcroft.

Struktur kontra expansion

För grafer som blandar tillväxthastigheter i olika skalor måste du använda en mängd olika tekniker.

Ett mycket användbart faktum är att, som Easo förklarade, "om en graf ser ut att växa långsamt i någon skala, då fastnar den." Den kommer att fortsätta växa långsamt i större skalor. Eftersom grafer med långsam tillväxt har ytterligare struktur som bestäms av en gren av matematiken som kallas gruppteori, var det också känt att om du zoomar ut tillräckligt långt visar grafer med långsam tillväxt geometri som är matematiskt tam.

År 2021 arbetade Sébastien Martineau från Sorbonne University i Paris, tillsammans med Daniel Contreras och Vincent Tassion från ETH Zürich, kunde använda denna egendom till bevisa Schramms lokalitetsförmodan för grafer som så småningom växer långsamt.

Vid denna tidpunkt hade de två grupperna av matematiker framgångsrikt tacklat gissningen från olika håll: snabb tillväxt och långsam tillväxt. Men detta lämnade stora luckor. För det första finns det en kategori med medeltillväxt som inte täcktes av Easo och Hutchcrofts teknik eller av Contreras, Martineau och Tassions bevis. Ett annat problem var att argumenten fortfarande inte gällde grafer med förändrade tillväxthastigheter - bara de som höll sig snabba eller höll sig långsamma. För att argumentet Contreras, Martineau och Tassion skulle kunna tillämpas på godtyckliga grafer räckte det inte med att geometrin så småningom ser tam ut när du zoomar ut, förklarade Easo: "Vi behöver att den ser tam ut nu, nära den nuvarande skalan."

The Middle of Nowhere

Transitiva grafer över medeltillväxt är mycket mystiska. Matematiker har aldrig hittat ett exempel på en transitiv graf vars tillväxt faller inom detta område. Det är möjligt att de inte ens existerar. Men matematiker har inte bevisat att de inte existerar, så alla fullständiga bevis på Schramms lokalitetsföreställningar måste ta itu med dem. Utöver utmaningen behövde Easo och Hutchcroft ta itu med grafer som kanske bara kortvarigt har en mellanliggande tillväxt på en viss längdskala, även om de växer snabbare eller långsammare när du zoomar in eller ut.

Easo och Hutchcroft tillbringade en stor del av det senaste året för att utöka sina resultat till att gälla grafer som inte täcktes av någon av de tidigare metoderna.

Först modifierade de 2018 års teknik som Hutchcroft hade tillämpat på snabbväxande grafer för att arbeta på grafer som ändrar tillväxtnivåer i olika skalor. De tacklade sedan fallet med långsam tillväxt, in ett 27-sidigt papper de delade i augusti som utökade arbetet med Contreras, Martineau och Tassion. Slutligen, i sitt förtryck i oktober, utarbetade de ett annat argument med hjälp av teorin om slumpmässiga promenader – linjer som vickar slumpmässigt genom rymden – för att hantera fallet med mellanliggande tillväxt. När trikotomien var klar, hade de bevisat Schramms lokalitetsföreställning.

"Vi var tvungna att kasta allt vi visste på problemet," sa Hutchcroft.

Lösningen ger matematiker en bättre inblick i vad som händer över perkolationströskeln, där chansen för ett oändligt kluster är 100 %, och under det, där chansen är 0 %. Men matematiker är fortfarande förvånade över vad som händer exakt vid tröskeln för de flesta grafer, inklusive det tredimensionella rutnätet. "Det är förmodligen den mest kända, mest grundläggande öppna frågan inom perkolationsteorin," sa Russell Lyons från Indiana University.

Det tvådimensionella rutnätet är ett av få fall där matematiker har bevisat vad som händer exakt vid tröskeln: oändliga kluster bildas inte. Och efter att Grimmett och Marstrand bevisat en version av lokalitetsförmodan för stora plattor, visade Grimmett och medarbetare att om du skär ett 3D-rutnät på mitten horisontellt, skapar ett golv och ställer in urtavlan exakt till perkolationströskeln, dyker inga oändliga kluster upp. Deras resultat antyder att det fullständiga tredimensionella rutnätet, liksom dess tvådimensionella motsvarighet, kanske inte har ett oändligt kluster vid perkolationströskeln.

1996, Benjamini och Schramm conjectured att chansen att hitta ett oändligt kluster precis vid tröskeln är noll för alla transitiva grafer – precis som det är för 2D-rutnätet eller för 3D-rutnätet delat på mitten. Nu när ortsförmodan har avgjorts kan en förståelse för vad som händer precis vid övergångspunkten vara lite närmare.

Rättelse: December 18, 2023
Antalet noder inom n länkar av en startnod på en 3-regelbunden graf växer till ungefär 2ⁿ, inte 3ⁿ som den här artikeln ursprungligen stod. Artikeln har korrigerats.

Quanta genomför en serie undersökningar för att bättre betjäna vår publik. Ta vår matematikläsarundersökning och du kommer att delta för att vinna gratis Quanta merch.