Et nærbillede afslører 'smeltepunktet' for en uendelig graf | Quanta Magasinet

I 2008 døde matematikeren Oded Schramm i en vandreulykke i Cascade-bjergene omkring 50 miles øst for Seattle. Selvom han kun var 46 år gammel, havde han konstrueret helt nye områder af matematik.

"Han var en fantastisk matematiker," sagde Itai Benjamini, matematiker ved Weizmann Institute of Science og Schramms ven og samarbejdspartner. "Ekstremt kreativ, ekstremt elegant, ekstremt original."

De spørgsmål, han stillede, skubber stadig grænserne for sandsynlighedsteori og statistisk fysik. Mange af disse spørgsmål vedrører matematiske strukturer, der har en faseovergang - en pludselig makroskopisk ændring, som is, der smelter til vand. Ligesom forskellige materialer har forskellige smeltepunkter, varierer faseovergange af matematiske strukturer også.

Schramm formodede, at faseovergangen i en proces kaldet perkolation kan estimeres ved kun at bruge et nærbillede af systemet - kaldet det lokale perspektiv - for mange vigtige matematiske strukturer. At zoome helt ud og se på det hele vil ikke ændre beregningen væsentligt. I de sidste 15 år har matematikere smidt små stykker af formodningen, men indtil nu har de ikke været i stand til helt at løse det.

I en fortryk udsendt i oktober, Tom Hutchcroft fra California Institute of Technology og hans ph.d.-studerende Philip Easo beviste Schramms lokalitetsformodning. Deres bevis bygger på store ideer fra sandsynlighedsteori og andre matematikområder, som de kombinerede på en smart måde.

"Det er et bemærkelsesværdigt papir. Det er en ophobning af langt arbejde," sagde Benjamini.

Uendelige klynger

Ordet "perkolation" refererede oprindeligt til væskens bevægelse gennem et porøst medium, såsom vand, der strømmer gennem kaffegrums eller olie, der siver gennem revner i en sten.

I 1957 udviklede matematikerne Simon Ralph Broadbent og John Michael Hammersley en matematisk model for denne fysiske proces. I årtierne siden er denne model blevet et genstand for undersøgelse i sig selv. Matematikere studerer perkolation, fordi det rammer en vigtig balance: Opsætningen er enkel, men den udviser komplekse og gådefulde funktioner.

"Det er en slags kanonisk model for matematikere," sagde Hutchcroft. "Man kan tænke på tingene visuelt. Det gør det rigtig rart at arbejde med.”

Perkolation starter med en graf, som er en samling af hjørner (punkter), der kan forbindes med kanter (linjer). Et af de enkleste eksempler er et firkantet gitter med hjørner på linje for at danne hjørnerne af firkanter og kanter, der forbinder nogle af dem.

Kort før sin død formodede Schramm, at Grimmett og Marstrands teorem kunne generaliseres. Han troede, at perkolationstærsklen bestemmes udelukkende af nærbilledet eller "mikroskopisk" perspektiv for en stor klasse af grafer kendt som transitive grafer.

I 2009, Benjamini, Asaf Nachmias , Yuval Peres bevist Schramms lokalitetsformodning, som den nu er kendt, for en specifik type transitiv graf, der ligner et træ. Schramm havde dog postuleret, at det ville holde for alle transitive grafer (med undtagelse for endimensionelle grafer).

I en transitiv graf ser alle hjørnerne ens ud. Et todimensionelt gitter er et eksempel. Hvis du vælger to vilkårlige hjørner, kan du altid finde en symmetri, der flytter det ene hjørne til det andet.

Dette forhold gælder for enhver transitiv graf. På grund af disse symmetrier vil de se ens ud, hvis du zoomer ind og ser på to lige store pletter af en transitiv graf. Af denne grund mente Schramm, at nærbilledet var tilstrækkeligt til at give matematikere mulighed for at beregne perkolationstærsklen for alle transitive grafer.

Transitive grafer kan antage mange former og former. De kan være et simpelt gitter, der består af firkanter, trekanter, sekskanter eller en anden form. Eller de kan danne et mere komplekst objekt, som et "3-regulært træ", hvor et centralt punkt forbindes til tre hjørner, og hvert hjørne forgrener sig for at skabe to nye ad infinitum, hvoraf de første par trin ses her:

Variationen af ​​transitive grafer bidrog til vanskeligheden ved at bevise Schramms lokalitetsformodning. I de 15 år, der gik mellem Schramms formodning og Easo og Hutchcrofts bevis, beviste forskellige grupper af matematikere formodningen for specifikke typer grafer, men deres ideer blev aldrig udvidet til det generelle tilfælde.

"Rummet for alle mulige geometrier er bare så stort, og der er altid underlige ting, der lurer," sagde Hutchcroft.

Udvidelse af objektivet

Easo og Hutchcroft ledte ikke oprindeligt efter en løsning på Schramms lokalitetsformodning, som gælder for uendelige grafer. De studerede i stedet perkolation på endelige grafer. Men de havde en idé, der pludselig flyttede deres opmærksomhed til formodningen.

"Vi kom op med dette nye værktøj, og vi tænkte, åh, det virker som noget, der kunne være nyttigt til at angribe lokalitet," sagde Easo.

For at bevise formodningen var de nødt til at vise, at det mikroskopiske perspektiv giver et nøjagtigt øjebliksbillede af perkolationstærsklen. Når du kun ser en del af en graf og observerer en stor forbundet klynge, kan du antage, at grafen har en uendelig klynge og derfor er over perkolationstærsklen. Easo og Hutchcroft satte sig for at bevise det.

De stolede på en teknik, der kan opfattes som "at udvide linsen." Start ved et enkelt toppunkt. Zoom derefter ud for at se alle hjørner, der kun er en kant væk på den originale graf. På det firkantede gitter vil du nu kunne se fem samlede hjørner. Udvid linsen igen for at se alle hjørner inden for en afstand af to kanter, og derefter en afstand på tre kanter, fire kanter og så videre.

Easo og Hutchcroft indstiller skiven, der bestemmer, hvor mange links der er tæt på, hvor de så en stor klynge. De udvidede derefter linsen og så flere og flere kanter samle sig i deres store klynge. Mens de gjorde det, skulle de øge sandsynligheden for, at links ville være til stede, hvilket gør det nemmere at vise, at grafen har en stor forbundet komponent. Dette er en delikat balancegang. De havde brug for at udvide synsfeltet hurtigt nok og tilføje links langsomt nok til at afsløre den fulde uendelige graf uden dramatisk at ændre urskivens position.

De var i stand til at vise, at store klynger vokser hurtigere end mindre, så, som Easo udtrykte det, "din klynge vokser hurtigere og hurtigere, efterhånden som den bliver større og større, ligesom når du ruller en snebold."

For kvadratgitteret vokser toppunktet relativt langsomt. Det er nogenlunde bredden af ​​dit objektiv i kvadrat. Efter 10 trin finder du omkring 100 hjørner. Men et 3-regulært træ vokser eksponentielt hurtigere - cirka 2 hævet til styrken af ​​din linsebredde. Efter 10 trin vil du se cirka 1,024 hjørner. Illustrationen nedenfor viser, hvordan det 3-regelmæssige træ er meget større efter kun syv trin, selvom det firkantede gitter har flere hjørner i starten. Generelt kan grafer have forskellige væksthastigheder på forskellige skalaer - de starter måske hurtigt og derefter bremses.

Tilbage i 2018, Hutchcroft brugt en lignende idé at bevise lokalitetsformodningen for hurtigt voksende grafer som det 3-regulære træ. Men det fungerede ikke for grafer med langsom vækst som kvadratgitteret eller for grafer, der vokser med mellemhastighed, og opfylder hverken de matematiske kriterier for hurtig vækst eller dem for langsom vækst.

"Det er her, tingene bliver virkelig frustrerende i tre år," sagde Hutchcroft.

Struktur versus udvidelse

For grafer, der blander vækstrater i forskellige skalaer, skal du bruge en række forskellige teknikker.

En meget nyttig kendsgerning er, som Easo forklarede, "hvis en graf ser langsom vækst ud i en eller anden skala, så sætter den sig fast." Det vil fortsætte med at vokse langsomt i større skalaer. Fordi grafer med langsom vækst har yderligere struktur bestemt af en gren af ​​matematikken kaldet gruppeteori, var det også kendt, at hvis du zoomer langt nok ud, viser grafer med langsom vækst en geometri, der er matematisk tam.

I 2021 arbejdede Sébastien Martineau fra Sorbonne Universitet i Paris sammen med Daniel Contreras og Vincent Tassion fra ETH Zürich, var i stand til at bruge denne ejendom til bevise Schramms lokalitetsformodning for grafer, der til sidst vokser langsomt.

På dette tidspunkt havde de to grupper af matematikere med succes tacklet formodningen fra forskellige retninger: hurtig vækst og langsom vækst. Men dette efterlod store huller. For det første er der en kategori med mellemvækst, der ikke var dækket af Easo og Hutchcrofts teknik eller af Contreras, Martineau og Tassions bevis. Et andet problem var, at argumenterne stadig ikke gjaldt grafer med skiftende vækstrater - kun dem, der forblev hurtige eller forblev langsom. For at Contreras, Martineau og Tassion-argumentet kan anvendes på vilkårlige grafer, var det ikke nok, at geometrien til sidst ser tam ud, når du zoomer ud, forklarede Easo: "Vi har brug for, at den ser tam ud nu, nær den nuværende skala."

The Middle of Nowhere

Transitive grafer for mellemvækst er meget mystiske. Matematikere har aldrig fundet et eksempel på en transitiv graf, hvis vækst falder i dette område. Det er muligt, at de ikke engang eksisterer. Men matematikere har ikke bevist, at de ikke eksisterer, så ethvert fuldstændigt bevis for Schramms lokalitetsformodning skal adressere dem. For at tilføje udfordringen var Easo og Hutchcroft nødt til at adressere grafer, som måske kun kortvarigt har mellemvækst på en bestemt længdeskala, selvom de vokser hurtigere eller langsommere, når du zoomer ind eller ud.

Easo og Hutchcroft brugte meget af det sidste år på at udvide deres resultater til at gælde for grafer, der ikke var dækket af nogen af ​​de tidligere metoder.

Først ændrede de 2018-teknikken, som Hutchcroft havde anvendt på hurtigtvoksende grafer, for at arbejde på grafer, der ændrer vækstniveauer i forskellige skalaer. De tog så fat på sagen med langsom vækst ind et papir på 27 sider de delte i august, at det udvidede arbejdet med Contreras, Martineau og Tassion. Til sidst, i deres fortryk fra oktober, udtænkte de endnu et argument ved at bruge teorien om tilfældige ture - linjer, der slingrer tilfældigt gennem rummet - for at håndtere tilfældet med mellemvækst. Med trikotomien fuldført havde de bevist Schramms lokalitetsformodning.

"Vi var nødt til at kaste alt, hvad vi vidste, på problemet," sagde Hutchcroft.

Løsningen giver matematikere et bedre indblik i, hvad der sker over perkolationstærsklen, hvor chancen for en uendelig klynge er 100 %, og under den, hvor chancen er 0 %. Men matematikere er stadig chokeret over, hvad der sker præcist ved tærsklen for de fleste grafer, inklusive det tredimensionelle gitter. "Det er nok det mest berømte, mest grundlæggende åbne spørgsmål i perkolationsteorien," sagde Russell Lyons fra Indiana University.

Det todimensionelle gitter er et af de få tilfælde, hvor matematikere har bevist, hvad der sker præcist ved tærsklen: uendelige klynger dannes ikke. Og efter at Grimmett og Marstrand havde bevist en version af lokalitetsformodningerne for store plader, viste Grimmett og samarbejdspartnere, at hvis du skærer et 3D-gitter i halve vandret, skaber et gulv og indstiller skiven nøjagtigt til perkolationstærsklen, vises ingen uendelige klynger. Deres resultat antyder, at det fulde tredimensionelle gitter, ligesom dets todimensionelle modstykke, muligvis ikke har en uendelig klynge ved perkolationstærsklen.

I 1996, Benjamini og Schramm formodede at chancen for at finde en uendelig klynge lige ved tærsklen er nul for alle transitive grafer - ligesom det er for 2D-gitteret eller for 3D-gitteret skåret i halve. Nu hvor lokalitetsformodningen er afgjort, er en forståelse af, hvad der sker lige ved overgangspunktet, måske bare en lille smule nærmere.

Rettelse: 18. December, 2023
Antallet af knudepunkter inden for n links af en startknude på en 3-regulær graf vokser som ca.ⁿ, ikke 3ⁿ som denne artikel oprindeligt sagde. Artiklen er blevet rettet.

Quanta gennemfører en række undersøgelser for bedre at kunne betjene vores publikum. Tag vores matematiklæserundersøgelse og du vil være med til at vinde gratis Quanta merch.