Pogled od blizu razkrije "tališče" neskončnega grafa | Revija Quanta

Leta 2008 je matematik Oded Schramm umrl v nesreči na pohodu v gorah Cascade, približno 50 milj vzhodno od Seattla. Čeprav je bil star le 46 let, je zgradil povsem nova področja matematike.

"Bil je fantastičen matematik," je rekel Itai Benjamini, matematik na Weizmannovem inštitutu za znanost ter Schrammov prijatelj in sodelavec. "Izjemno kreativno, izjemno elegantno, izjemno izvirno."

Vprašanja, ki jih je postavil, še vedno premikajo meje teorije verjetnosti in statistične fizike. Mnoga od teh vprašanj se nanašajo na matematične strukture, ki imajo fazni prehod - nenadno makroskopsko spremembo, kot je taljenje ledu v vodo. Tako kot imajo različni materiali različna tališča, se razlikujejo tudi fazni prehodi matematičnih struktur.

Schramm je domneval, da je fazni prehod v procesu, imenovanem perkolacija, mogoče oceniti z uporabo samo bližnjega pogleda na sistem - imenovanega lokalna perspektiva - za številne pomembne matematične strukture. Pomanjšanje do konca in pogled v celoti ne bo bistveno spremenil izračuna. V zadnjih 15 letih so matematiki drobno odrezali domnevo, vendar je do zdaj niso mogli popolnoma razrešiti.

V prednatis objavljen oktobra, Tom Hutchcroft s Kalifornijskega tehnološkega inštituta in njegov doktorski študent Filip Easo dokazal Schrammovo lokalno domnevo. Njihov dokaz temelji na glavnih zamislih iz teorije verjetnosti in drugih področij matematike, ki sta jih združila na pameten način.

»To je izjemen papir. To je akumulacija dolgega dela,« je dejal Benjamini.

Neskončni grozdi

Beseda "perkolacija" se je prvotno nanašala na gibanje tekočine skozi porozni medij, kot je voda, ki teče skozi kavno usedlino, ali olje, ki pronica skozi razpoke v skali.

Leta 1957 sta matematika Simon Ralph Broadbent in John Michael Hammersley razvila matematični model tega fizičnega procesa. V desetletjih od takrat je ta model postal samostojen predmet preučevanja. Matematiki preučujejo perkolacijo, ker vzpostavlja pomembno ravnotežje: postavitev je preprosta, vendar kaže zapletene in zagonetne značilnosti.

"To je nekakšen kanonični model za matematike," je dejal Hutchcroft. »Stvari si lahko zamislite vizualno. Zaradi tega je zelo lepo delati z njim.«

Perkolacija se začne z grafom, ki je zbirka vozlišč (točk), ki jih je mogoče povezati z robovi (črtami). Eden najpreprostejših primerov je kvadratna mreža z oglišči, ki so poravnana tako, da tvorijo vogale kvadratov, in robovi, ki povezujejo nekatere izmed njih.

Malo pred svojo smrtjo je Schramm domneval, da je Grimmettov in Marstrandov izrek mogoče posplošiti. Menil je, da je perkolacijski prag v celoti določen z bližnjim ali "mikroskopskim" vidikom za velik razred grafov, znanih kot tranzitivni grafi.

Leta 2009 je Benjamini, Asaf Nachmias in Yuval Peres dokazano Schrammova lokalnostna domneva, kot je zdaj znana, za specifično vrsto tranzitivnega grafa, ki je podoben drevesu. Schramm pa je domneval, da bo veljalo za vse tranzitivne grafe (z izjemo enodimenzionalnih grafov).

V tranzitivnem grafu so vsa vozlišča videti podobna. Eden od primerov je dvodimenzionalna mreža. Če izberete kateri koli dve točki, lahko vedno najdete simetrijo, ki premakne eno točko v drugo.

To razmerje velja za vsak tranzitivni graf. Zaradi teh simetrij bosta, če povečate in pogledate katera koli dva enako velika zaplata tranzitivnega grafa, videti enako. Iz tega razloga je Schramm verjel, da perspektiva od blizu zadostuje, da matematikom omogoči izračun perkolacijskega praga za vse tranzitivne grafe.

Tranzitivni grafi imajo lahko veliko oblik in oblik. Lahko so preprosta mreža, sestavljena iz kvadratov, trikotnikov, šesterokotnikov ali kakšne druge oblike. Lahko pa tvorijo bolj zapleten objekt, kot je "3-pravilno drevo", kjer se ena središčna točka povezuje s tremi vozlišči, vsako vozlišče pa se nato razveji in ustvari dve novi ad infinitum, katerih prvih nekaj korakov je vidnih tukaj:

Raznolikost tranzitivnih grafov je prispevala k težavam pri dokazovanju Schrammove domneve o lokalnosti. V 15 letih med Schrammovo domnevo in Easovim in Hutchcroftovim dokazom so različne skupine matematikov dokazale domnevo za posebne vrste grafov, vendar se njihove ideje nikoli niso razširile na splošni primer.

"Prostor vseh možnih geometrij je tako ogromen in vedno se skrivajo čudne stvari," je dejal Hutchcroft.

Razširitev leče

Easo in Hutchcroft sprva nista iskala rešitve za Schrammovo lokalno domnevo, ki velja za neskončne grafe. Namesto tega so proučevali perkolacijo na končnih grafih. Vendar so imeli idejo, ki je nenadoma preusmerila njihovo pozornost na domnevo.

"Omislili smo si to novo orodje in pomislili smo, oh, to se zdi nekaj, kar bi lahko bilo koristno za napad na lokalnost," je dejal Easo.

Da bi dokazali domnevo, so morali pokazati, da mikroskopska perspektiva daje natančen posnetek praga perkolacije. Ko si ogledate le del grafa in opazujete veliko povezano gručo, lahko domnevate, da ima graf neskončno gručo in je zato nad perkolacijskim pragom. Easo in Hutchcroft sta se odločila to dokazati.

Zanašali so se na tehniko, ki jo lahko razumemo kot "razširitev leče". Začnite pri eni točki. Nato pomanjšajte, da si ogledate vsa oglišča, ki so na izvirnem grafu oddaljena le en rob. Na kvadratni mreži boste zdaj lahko videli skupno pet točk. Znova razširite lečo, da vidite vsa oglišča na razdalji dveh robov, nato pa na razdalji treh robov, štirih robov itd.

Easo in Hutchcroft nastavita številčnico, ki določa, koliko povezav je blizu mesta, kjer sta videla veliko gručo. Nato so razširili lečo in opazovali, kako se vse več robov zbira v njihovi veliki gruči. Pri tem so morali povečati verjetnost, da bodo povezave prisotne, kar olajša prikaz, da ima graf veliko povezano komponento. To je občutljivo ravnotežje. Dovolj hitro so morali razširiti vidno polje in dovolj počasi dodajati povezave, da so razkrili celoten neskončni graf brez dramatične spremembe položaja številčnice.

Uspelo jim je pokazati, da veliki grozdi rastejo hitreje kot manjši, tako da, kot je dejal Easo, "vaš grozd raste hitreje in hitreje, ko postaja večji in večji, tako kot ko kotalite snežno kepo."

Pri kvadratni mreži število vozlišč raste razmeroma počasi. To je približno širina vaše leče na kvadrat. Po 10 korakih boste našli približno 100 oglišč. Toda 3-pravilno drevo raste eksponentno hitreje - približno 2, dvignjeno na potenco širine vaše leče. Po 10 korakih boste videli približno 1,024 oglišč. Spodnja ilustracija prikazuje, kako je 3-pravilno drevo veliko večje že po sedmih korakih, čeprav ima kvadratna mreža na začetku več oglišč. Na splošno imajo lahko grafi različne stopnje rasti na različnih lestvicah – lahko začnejo hitro, nato pa se upočasnijo.

Nazaj v 2018, Hutchcroft uporabil podobno idejo dokazati domnevo o lokalnosti za hitro rastoče grafe, kot je 3-pravilno drevo. Vendar ni delovalo za grafe s počasno rastjo, kot je kvadratna mreža, ali za grafe, ki rastejo s srednjo hitrostjo in ne izpolnjujejo niti matematičnih meril za hitro rast niti tistih za počasno rast.

"Tukaj postanejo stvari res frustrirajoče za približno tri leta," je dejal Hutchcroft.

Struktura proti širitvi

Za grafe, ki mešajo stopnje rasti na različnih lestvicah, morate uporabiti različne tehnike.

Eno zelo koristno dejstvo je, kot je razložil Easo, "če je graf v nekem obsegu videti kot počasna rast, potem se zatakne." Še naprej bo počasi rasla v večjem obsegu. Ker imajo grafi počasne rasti dodatno strukturo, ki jo določa veja matematike, imenovana teorija skupin, je bilo tudi znano, da če dovolj pomanjšate, grafi počasne rasti prikazujejo geometrijo, ki je matematično skromna.

Leta 2021 je Sébastien Martineau z Univerze Sorbona v Parizu sodeloval z Danielom Contrerasom in Vincent Tassion ETH Zürich, lahko uporabil to lastnino za dokažite Schrammovo lokalno domnevo za grafe, ki sčasoma rastejo počasi.

Na tej točki sta se dve skupini matematikov uspešno lotili domneve iz različnih smeri: hitro rastočih in počasi rastočih. Toda to je pustilo precejšnje vrzeli. Prvič, obstaja kategorija vmesne rasti, ki ni bila zajeta v Easovi in ​​Hutchcroftovi tehniki ali v dokazih Contrerasa, Martineauja in Tassiona. Druga težava je bila, da argumenti še vedno niso veljali za grafe s spreminjajočimi se stopnjami rasti – samo za tiste, ki so ostali hitri ali počasni. Za uporabo argumentov Contrerasa, Martineauja in Tassiona na poljubnih grafih ni bilo dovolj, da je geometrija sčasoma videti skromna, ko pomanjšate, je pojasnil Easo: "Potrebujemo, da je zdaj videti krotka, blizu trenutnega obsega."

Sredina ničesar

Tranzitivni grafi vmesne rasti so zelo skrivnostni. Matematiki še nikoli niso našli primera tranzitivnega grafa, katerega rast pade v to območje. Možno je, da sploh ne obstajajo. Toda matematiki niso dokazali, da ne obstajajo, zato jih mora obravnavati vsak popoln dokaz Schrammove domneve o lokalnosti. Poleg tega sta morala Easo in Hutchcroft obravnavati grafe, ki imajo lahko le za kratek čas vmesno rast na določeni lestvici dolžine, tudi če rastejo hitreje ali počasneje, ko povečate ali pomanjšate.

Easo in Hutchcroft sta večino preteklega leta porabila za razširitev svojih rezultatov na grafe, ki jih ni zajela nobena od prejšnjih metod.

Najprej so spremenili tehniko iz leta 2018, ki jo je Hutchcroft uporabil za hitro rastoče grafe, da bi delali na grafih, ki spreminjajo stopnje rasti na različnih lestvicah. Nato so se lotili počasnega primera, v 27-stranski papir so delili avgusta, ki je razširil delo na Contrerasu, Martineauju in Tassionu. Nazadnje so v svojem oktobrskem prednatisu oblikovali še en argument z uporabo teorije naključnih sprehodov – črt, ki se naključno premikajo skozi vesolje – za obravnavo primera vmesne rasti. S končano trihotomijo so dokazali Schrammovo lokalno domnevo.

"Problemu smo morali dati vse, kar smo vedeli," je dejal Hutchcroft.

Rešitev daje matematikom boljši vpogled v dogajanje nad perkolacijskim pragom, kjer je možnost neskončnega grozda 100 %, in pod njim, kjer je možnost 0 %. Toda matematiki so še vedno v zadregi, kaj se zgodi točno na pragu za večino grafov, vključno s tridimenzionalno mrežo. "To je verjetno najbolj znano, najbolj osnovno odprto vprašanje v teoriji perkolacije," je dejal Russell Lyons univerze Indiana.

Dvodimenzionalna mreža je eden redkih primerov, kjer so matematiki dokazali, kaj se zgodi točno na pragu: neskončni grozdi se ne oblikujejo. In potem ko sta Grimmett in Marstrand dokazala različico domneve o lokalnosti za velike plošče, so Grimmett in sodelavci pokazali, da če 3D-mrežo vodoravno prerežete na polovico, s čimer ustvarite tla, in številčnico nastavite natančno na prag perkolacije, se ne prikažejo neskončni grozdi. Njihov rezultat namiguje, da polna tridimenzionalna mreža, tako kot njen dvodimenzionalni dvojnik, morda nima neskončnega grozda na perkolacijskem pragu.

Leta 1996 sta Benjamini in Schramm domneval da je možnost, da najdemo neskončno gručo tik na pragu, enaka nič za vse tranzitivne grafe — tako kot velja za 2D mrežo ali za 3D mrežo, prerezano na pol. Zdaj, ko je domneva o lokalnosti potrjena, je morda razumevanje tega, kaj se zgodi prav na točki prehoda, le malo bližje.

Popravek: December 18, 2023
Število vozlišč znotraj n povezav začetnega vozlišča na 3-pravilnem grafu raste približno kot 2ⁿ, ne 3ⁿ kot je prvotno navedeno v tem članku. Članek je bil popravljen.

Quanta izvaja vrsto anket, da bi bolje služil svojemu občinstvu. Vzemite našo anketa bralcev matematike in vključeni boste v brezplačno zmago Quanta roba.