Et nærbilde avslører "smeltepunktet" til en uendelig graf | Quanta Magazine

I 2008 døde matematikeren Oded Schramm i en turulykke i Cascade-fjellene rundt 50 mil øst for Seattle. Selv om han bare var 46 år gammel, hadde han konstruert helt nye områder innen matematikk.

"Han var en fantastisk matematiker," sa Itai Benjamini, en matematiker ved Weizmann Institute of Science og Schramms venn og samarbeidspartner. "Ekstremt kreativ, ekstremt elegant, ekstremt original."

Spørsmålene han stilte presser fortsatt grensene for sannsynlighetsteori og statistisk fysikk. Mange av disse spørsmålene gjelder matematiske strukturer som har en faseovergang - en plutselig makroskopisk endring, som is som smelter til vann. Akkurat som forskjellige materialer har forskjellige smeltepunkter, varierer også faseoverganger til matematiske strukturer.

Schramm antok at faseovergangen i en prosess kalt perkolering kan estimeres ved å bruke bare et nærbilde av systemet - kalt det lokale perspektivet - for mange viktige matematiske strukturer. Å zoome helt ut og se på hele greia vil ikke endre beregningen nevneverdig. I løpet av de siste 15 årene har matematikere sløyfet små biter av formodningen, men til nå har de ikke klart å løse det fullstendig.

I en fortrykk lagt ut i oktober, Tom Hutchcroft ved California Institute of Technology og hans doktorgradsstudent Philip Easo beviste Schramms lokalitetsformodning. Beviset deres er avhengig av store ideer fra tvers av sannsynlighetsteori og andre områder av matematikk, som de kombinerte på en smart måte.

"Det er et bemerkelsesverdig papir. Det er en opphopning av langt arbeid," sa Benjamini.

Uendelige klynger

Ordet "perkolering" refererte opprinnelig til bevegelse av væske gjennom et porøst medium, for eksempel vann som strømmer gjennom kaffegrut eller olje som siver gjennom sprekker i en stein.

I 1957 utviklet matematikerne Simon Ralph Broadbent og John Michael Hammersley en matematisk modell av denne fysiske prosessen. I tiårene siden har denne modellen blitt et studieobjekt i seg selv. Matematikere studerer perkolering fordi det finner en viktig balanse: Oppsettet er enkelt, men det viser komplekse og forvirrende funksjoner.

"Det er en slags kanonisk modell for matematikere," sa Hutchcroft. «Du kan tenke på ting visuelt. Det gjør den veldig fin å jobbe med.»

Perkolering starter med en graf, som er en samling av hjørner (punkter) som kan forbindes med kanter (linjer). Et av de enkleste eksemplene er et firkantet rutenett, med hjørner på linje for å danne hjørnene av firkanter og kanter som forbinder noen av dem.

Rett før hans død antok Schramm at Grimmett og Marstrands teorem kunne generaliseres. Han trodde at perkolasjonsterskelen helt og holdent bestemmes av nærbildet, eller "mikroskopisk" perspektiv for en stor klasse grafer kjent som transitive grafer.

I 2009, Benjamini, Asaf Nachmias og Yuval Peres beviste Schramms lokalitetsformodning, som den nå er kjent, for en spesifikk type transitiv graf som ligner et tre. Schramm hadde imidlertid postulert at det ville gjelde for alle transitive grafer (med unntak for endimensjonale grafer).

I en transitiv graf ser alle toppunktene like ut. Et todimensjonalt rutenett er ett eksempel. Hvis du velger to hjørner, kan du alltid finne en symmetri som flytter det ene hjørnet til det andre.

Dette forholdet gjelder for enhver transitiv graf. På grunn av disse symmetriene, hvis du zoomer inn og ser på to like store flekker i en transitiv graf, vil de se like ut. Av denne grunn mente Schramm at nærbildeperspektivet var tilstrekkelig til å tillate matematikere å beregne perkolasjonsterskelen for alle transitive grafer.

Transitive grafer kan ha mange former og former. De kan være et enkelt rutenett, laget av firkanter, trekanter, sekskanter eller en annen form. Eller de kan danne et mer komplekst objekt, som et "3-regelmessig tre", der ett sentralt punkt kobles til tre toppunkter, og hvert toppunkt deretter forgrener seg for å lage to nye ad infinitum, de første trinnene av disse er sett her:

Variasjonen av transitive grafer bidro til vanskeligheten med å bevise Schramms lokalitetsformodning. I løpet av de 15 årene mellom Schramms formodning og Easo og Hutchcrofts bevis, beviste forskjellige grupper av matematikere formodningen for spesifikke typer grafer, men ideene deres utvidet seg aldri til det generelle tilfellet.

"Rummen til alle mulige geometrier er bare så enorm, og det er alltid rare ting som lurer," sa Hutchcroft.

Utvide linsen

Easo og Hutchcroft var i utgangspunktet ikke ute etter en løsning på Schramms lokalitetsformodning, som gjelder uendelige grafer. De studerte i stedet perkolasjon på endelige grafer. Men de hadde en idé som plutselig flyttet oppmerksomheten deres til formodningen.

"Vi kom opp med dette nye verktøyet, og vi tenkte, åh, dette virker som en ting som kan være nyttig for å angripe lokalitet," sa Easo.

For å bevise formodningen, trengte de å vise at det mikroskopiske perspektivet gir et nøyaktig øyeblikksbilde av perkolasjonsterskelen. Når du bare ser en del av en graf og observerer en stor sammenkoblet klynge, kan du anta at grafen har en uendelig klynge og derfor er over perkolasjonsterskelen. Easo og Hutchcroft forsøkte å bevise det.

De stolte på en teknikk som kan tenkes å "utvide linsen." Start ved et enkelt toppunkt. Zoom deretter ut for å se alle toppunktene som er bare én kant unna på den originale grafen. På det firkantede rutenettet vil du nå kunne se fem totale toppunkter. Utvid linsen igjen for å se alle hjørner innenfor en avstand på to kanter, og deretter en avstand på tre kanter, fire kanter og så videre.

Easo og Hutchcroft setter skiven som bestemmer hvor mange lenker det er i nærheten av der de så en stor klynge. De utvidet deretter linsen og så flere og flere kanter samle seg i den store klyngen deres. Mens de gjorde det, måtte de øke sannsynligheten for at koblinger ville være tilstede, noe som gjør det lettere å vise at grafen har en stor koblet komponent. Dette er en delikat balansegang. De trengte å utvide synsfeltet raskt nok og legge til lenker sakte nok til å avsløre hele den uendelige grafen uten å dramatisk endre posisjonen til skiven.

De var i stand til å vise at store klynger vokser raskere enn mindre, slik at, som Easo sa det, "klyngen din vokser raskere og raskere ettersom den blir større og større, akkurat som når du ruller en snøball."

For kvadratnettet vokser toppunktantallet relativt sakte. Det er omtrent bredden på linsen din i kvadrat. Etter 10 trinn finner du rundt 100 hjørner. Men et 3-regelmessig tre vokser eksponentielt raskere - omtrent 2 hevet til kraften til linsebredden din. Etter 10 trinn vil du se omtrent 1,024 hjørner. Illustrasjonen nedenfor viser hvordan det 3-regulære treet er mye større etter bare syv trinn, selv om det firkantede rutenettet har flere hjørner i begynnelsen. Generelt kan grafer ha forskjellige veksthastigheter på forskjellige skalaer - de kan starte raskt, og deretter bremse ned.

Tilbake i 2018, Hutchcroft brukte en lignende idé for å bevise lokalitetsformodningen for raskt voksende grafer som det 3-regulære treet. Men det fungerte ikke for grafer med sakte vekst som kvadratnettet, eller for grafer som vokser med middels hastighet, og oppfyller verken de matematiske kriteriene for rask vekst eller de for langsom vekst.

"Det er her ting blir veldig frustrerende i tre år," sa Hutchcroft.

Struktur versus utvidelse

For grafer som blander veksthastigheter i forskjellige skalaer, må du bruke en rekke teknikker.

Et veldig nyttig faktum er at, som Easo forklarte, "hvis en graf ser saktevekst ut i en eller annen skala, så setter den seg fast." Den vil fortsette å vokse sakte i større skalaer. Fordi grafer med langsom vekst har ytterligere struktur bestemt av en gren av matematikken kalt gruppeteori, var det også kjent at hvis du zoomer langt nok ut, viser grafer med langsom vekst en matematisk tam geometri.

I 2021 jobbet Sébastien Martineau fra Sorbonne University i Paris, sammen med Daniel Contreras og Vincent Tassion fra ETH Zurich, var i stand til å bruke denne eiendommen til bevise Schramms lokalitetsformodning for grafer som til slutt vokser sakte.

På dette tidspunktet hadde de to gruppene av matematikere taklet formodningen fra forskjellige retninger: rask vekst og langsom vekst. Men dette etterlot store hull. For det første er det en kategori med middels vekst som ikke ble dekket av Easo og Hutchcrofts teknikk eller av Contreras, Martineau og Tassions bevis. Et annet problem var at argumentene fortsatt ikke gjaldt grafer med skiftende vekstrater - bare de som holdt seg raske eller holdt seg sakte. For at Contreras, Martineau og Tassion-argumentet skulle brukes på vilkårlige grafer, var det ikke nok at geometrien til slutt ser tam ut når du zoomer ut, forklarte Easo: "Vi trenger at den ser tam ut nå, nær gjeldende skala."

Midt i ingensteds

Transitive grafer over middels vekst er veldig mystiske. Matematikere har aldri funnet et eksempel på en transitiv graf hvis vekst faller i dette området. Det er mulig at de ikke engang eksisterer. Men matematikere har ikke bevist at de ikke eksisterer, så ethvert fullstendig bevis på Schramms lokalitetsformodning må adressere dem. I tillegg til utfordringen trengte Easo og Hutchcroft å adressere grafer som kanskje bare kortvarig har mellomvekst i en bestemt lengdeskala, selv om de vokser raskere eller saktere når du zoomer inn eller ut.

Easo og Hutchcroft brukte store deler av det siste året på å utvide resultatene til å gjelde grafer som ikke ble dekket av noen av de tidligere metodene.

Først endret de 2018-teknikken som Hutchcroft hadde brukt på raskt voksende grafer for å jobbe med grafer som endrer vekstnivåer i forskjellige skalaer. De taklet deretter saktevekstsaken, inn et papir på 27 sider de delte i august som utvidet arbeidet med Contreras, Martineau og Tassion. Til slutt, i sitt fortrykk i oktober, utviklet de et annet argument ved å bruke teorien om tilfeldige turer – linjer som slingrer seg tilfeldig gjennom rommet – for å håndtere tilfellet med mellomvekst. Med trikotomien fullført, hadde de bevist Schramms lokalitetsformodning.

"Vi måtte kaste alt vi visste på problemet," sa Hutchcroft.

Løsningen gir matematikere et bedre innblikk i hva som skjer over perkolasjonsterskelen, hvor sjansen for en uendelig klynge er 100 %, og under den, hvor sjansen er 0 %. Men matematikere stusser fortsatt over hva som skjer nøyaktig ved terskelen for de fleste grafer, inkludert det tredimensjonale rutenettet. "Det er sannsynligvis det mest kjente, mest grunnleggende åpne spørsmålet i perkolasjonsteori," sa Russell Lyons fra Indiana University.

Det todimensjonale rutenettet er et av få tilfeller der matematikere har bevist hva som skjer nøyaktig ved terskelen: uendelige klynger dannes ikke. Og etter at Grimmett og Marstrand beviste en versjon av lokalitetsformodningen for store plater, viste Grimmett og samarbeidspartnere at hvis du deler et 3D-rutenett i to horisontalt, skaper et gulv og justerer skiven nøyaktig til perkolasjonsterskelen, vises ingen uendelige klynger. Resultatet deres antyder at det fullstendige tredimensjonale rutenettet, som dets todimensjonale motstykke, kanskje ikke har en uendelig klynge ved perkoleringsterskelen.

I 1996, Benjamini og Schramm formodet at sjansen for å finne en uendelig klynge rett ved terskelen er null for alle transitive grafer – akkurat som det er for 2D-rutenettet eller for 3D-rutenettet delt i to. Nå som lokalitetsformodningen er avgjort, kan en forståelse av hva som skjer rett ved overgangspunktet bare være litt nærmere.

Korreksjon: Desember 18, 2023
Antall noder innenfor n lenker til en startnode på en 3-regulær graf vokser til omtrent 2ⁿ, ikke 3ⁿ som denne artikkelen opprinnelig sa. Artikkelen er rettet.

Quanta gjennomfører en serie undersøkelser for å tjene publikum bedre. Ta vår matematikk leserundersøkelse og du vil bli registrert for å vinne gratis Quanta varer.