A közeli nézet egy végtelen gráf „olvadáspontját” mutatja | Quanta Magazin

2008-ban Oded Schramm matematikus túrabalesetben halt meg a Cascade-hegységben, mintegy 50 mérföldre Seattle-től keletre. Noha mindössze 46 éves volt, teljesen új matematikai területeket épített fel.

„Fantasztikus matematikus volt” – mondta Itai Benjamini, a Weizmann Tudományos Intézet matematikusa és Schramm barátja és munkatársa. „Rendkívül kreatív, rendkívül elegáns, rendkívül eredeti.”

Az általa feltett kérdések még mindig a valószínűségszámítás és a statisztikai fizika határait feszegetik. E kérdések közül sok olyan matematikai struktúrákra vonatkozik, amelyek fázisátalakulással rendelkeznek – egy hirtelen makroszkopikus változás, például a jég vízzé olvadása. Ahogy a különböző anyagoknak eltérő olvadáspontjuk van, a matematikai szerkezetek fázisátalakulásai is eltérőek.

Schramm úgy sejtette, hogy a perkolációnak nevezett folyamat fázisátalakulását csak a rendszer közeli nézetének – az úgynevezett lokális perspektívának – felhasználásával lehet megbecsülni számos fontos matematikai struktúra esetében. Ha teljesen kicsinyíted és megnézed az egészet, az nem változtat jelentősen a számításon. Az elmúlt 15 évben a matematikusok feldarabolták a sejtés apró darabjait, de mindeddig nem tudták teljesen megoldani.

egy októberben feladott előnyomat, Tom Hutchcroft a California Institute of Technology munkatársa és doktorandusza Philip Easo bebizonyította Schramm lokalitássejtését. Bizonyításuk a valószínűségszámítás és a matematika más területeiből származó főbb ötletekre támaszkodik, amelyeket ügyesen kombináltak.

„Ez egy figyelemre méltó papír. Ez egy hosszú munka halmozódása” – mondta Benjamini.

Végtelen klaszterek

A „perkoláció” szó eredetileg a folyadék porózus közegben történő mozgására utalt, például a kávézaccon átfolyó vízre vagy a kőrepedéseken átszivárgó olajra.

1957-ben Simon Ralph Broadbent és John Michael Hammersley matematikusok kidolgozták ennek a fizikai folyamatnak a matematikai modelljét. Az azóta eltelt évtizedekben ez a modell önmagában is a kutatás tárgyává vált. A matematikusok a perkolációt tanulmányozzák, mert fontos egyensúlyt teremt: A beállítás egyszerű, de összetett és rejtélyes jellemzőket mutat.

„Ez egyfajta kanonikus modell a matematikusok számára” – mondta Hutchcroft. „El tudod képzelni a dolgokat vizuálisan. Ettől igazán jó vele dolgozni.”

A perkoláció egy gráftal kezdődik, amely élekkel (vonalakkal) összekapcsolható csúcsok (pontok) gyűjteménye. Az egyik legegyszerűbb példa a négyzetrács, ahol a csúcsok sorba rendeződnek, így alkotják a négyzetek sarkait és néhányat összekötő éleket.

Nem sokkal halála előtt Schramm úgy sejtette, hogy Grimmett és Marstrand tétele általánosítható. Úgy gondolta, hogy a perkolációs küszöböt teljes egészében a közeli vagy „mikroszkópos” perspektíva határozza meg a tranzitív gráfoknak nevezett gráfok nagy csoportjában.

2009-ben Benjamini, Asaf Nachmias és a Yuval Peres bizonyított Schramm lokalitási sejtése, ahogyan ma ismert, egy fára emlékeztető tranzitív gráf egy bizonyos típusára. Schramm azonban azt feltételezte, hogy ez minden tranzitív gráfra érvényes (az egydimenziós gráfok kivételével).

Egy tranzitív gráfban az összes csúcs hasonlónak tűnik. Egy példa erre a kétdimenziós rács. Ha bármelyik két csúcsot kiválasztja, mindig találhat olyan szimmetriát, amely az egyik csúcsot a másikba helyezi.

Ez az összefüggés minden tranzitív gráfra érvényes. Ezen szimmetriák miatt, ha ráközelítünk és megnézünk egy tranzitív gráf bármely két azonos méretű foltját, akkor ugyanúgy fognak kinézni. Emiatt Schramm úgy vélte, hogy a közeli perspektíva elegendő ahhoz, hogy a matematikusok minden tranzitív gráfra kiszámítsák a perkolációs küszöböt.

A tranzitív gráfok sokféle alakot és formát ölthetnek. Lehetnek egyszerű rácsok, négyzetekből, háromszögekből, hatszögekből vagy más formákból. Vagy alkothatnak egy összetettebb objektumot, például egy „3-szabályos fát”, ahol egy központi pont három csúcshoz kapcsolódik, majd mindegyik csúcs elágazik, és a végtelenségig két újat hoz létre, amelyek első néhány lépése itt látható:

A tranzitív gráfok sokfélesége hozzájárult a Schramm-féle lokalitássejtés bizonyításának nehézségéhez. A Schramm sejtése és Easo és Hutchcroft bizonyítása között eltelt 15 év alatt a matematikusok különböző csoportjai bizonyos típusú gráfok esetében bizonyították a sejtést, de elképzeléseik soha nem terjedtek ki az általános esetre.

„Az összes lehetséges geometria tere olyan hatalmas, és mindig furcsa dolgok rejtőznek” – mondta Hutchcroft.

A lencse szélesítése

Easo és Hutchcroft kezdetben nem kereste a megoldást Schramm lokalitási sejtésére, amely a végtelen gráfokra vonatkozik. Ehelyett a perkolációt tanulmányozták véges gráfokon. De támadt egy ötletük, ami hirtelen a sejtésre terelte figyelmüket.

„Kitaláltuk ezt az új eszközt, és azt gondoltuk, ó, ez olyan dolognak tűnik, amely hasznos lehet a hely megtámadásában” – mondta Easo.

A sejtés bizonyításához be kellett mutatniuk, hogy a mikroszkopikus perspektíva pontos pillanatképet ad a perkolációs küszöbről. Ha egy grafikonnak csak egy részét tekinti meg, és egy nagy összefüggő klasztert figyel meg, feltételezheti, hogy a gráfnak végtelen klasztere van, és ezért a perkolációs küszöb felett van. Easo és Hutchcroft nekiállt bizonyítani.

Olyan technikára támaszkodtak, amely a „lencse kiszélesítésének” tekinthető. Kezdje egyetlen csúcson. Ezután kicsinyítsen, hogy megtekinthesse az összes olyan csúcsot, amely csak egy éllel távolabb van az eredeti gráfon. A négyzetrácson most összesen öt csúcsot fog látni. Szélesítse újra a lencsét, hogy lássa az összes csúcsot két él távolságán belül, majd három él távolságot, négy élt és így tovább.

Easo és Hutchcroft beállította azt a tárcsát, amely meghatározza, hogy hány link van közel ahhoz, ahol egy nagy klasztert láttak. Ezután kiszélesítették a lencsét, és azt figyelték, hogy egyre több él gyűlik össze nagy fürtjükben. Ennek során növelniük kellett a hivatkozások előfordulásának valószínűségét, ami megkönnyíti annak kimutatását, hogy a grafikonnak nagy összefüggő összetevője van. Ez egy kényes egyensúlyozás. Elég gyorsan ki kellett tágítaniuk a látómezőt, és elég lassan kellett hivatkozásokat hozzáadniuk ahhoz, hogy a teljes végtelen grafikont a tárcsa helyzetének drámai megváltoztatása nélkül fedjék fel.

Meg tudták mutatni, hogy a nagy klaszterek gyorsabban nőnek, mint a kisebbek, így – ahogy Easo fogalmazott – „a klasztered egyre gyorsabban nő, ahogy egyre nagyobb és nagyobb, akárcsak ha hógolyót gurítasz”.

A négyzetrács esetében a csúcsok száma viszonylag lassan növekszik. Ez nagyjából az objektív szélessége négyzetesen. 10 lépés után körülbelül 100 csúcsot talál. De egy 3 szabályos fa exponenciálisan gyorsabban növekszik – nagyjából 2-vel a lencseszélesség erejéig. 10 lépés után körülbelül 1,024 csúcsot fog látni. Az alábbi ábra azt mutatja, hogy a 3 szabályos fa már hét lépés után sokkal nagyobb, bár a négyzetrácsnak eleinte több csúcsa van. Általánosságban elmondható, hogy a grafikonok eltérő növekedési rátákkal rendelkeznek különböző léptékekben – előfordulhat, hogy gyorsan indulnak, majd lelassulnak.

Még 2018-ban, Hutchcroft hasonló ötletet használt hogy bebizonyítsuk a lokalitási sejtést olyan gyorsan növekvő gráfoknál, mint a 3-reguláris fa. De nem működött lassú növekedésű grafikonoknál, mint például a négyzetrács, vagy olyan grafikonoknál, amelyek közepes sebességgel nőnek, és nem felelnek meg sem a gyors növekedés, sem a lassú növekedés matematikai kritériumainak.

„Itt a dolgok nagyon frusztrálóvá válnak három évig” – mondta Hutchcroft.

Struktúra kontra bővítés

A különböző léptékű növekedési ütemeket keverő grafikonokhoz többféle technikát kell alkalmazni.

Az egyik nagyon hasznos tény az, hogy – ahogy Easo kifejtette – „ha egy grafikon bizonyos léptékben lassú növekedésnek tűnik, akkor elakad”. Nagyobb léptékben lassan tovább fog növekedni. Mivel a lassú növekedésű grafikonoknak a matematika csoportelméletnek nevezett ága által meghatározott további szerkezetük van, az is ismert volt, hogy ha elég messzire kicsinyít, a lassú növekedésű grafikonok matematikailag szelíd geometriát jelenítenek meg.

2021-ben Sébastien Martineau, a párizsi Sorbonne Egyetem munkatársa, Daniel Contreras és Vincent Tassion az ETH Zürich, használhatta ezt az ingatlant bizonyítja Schramm lokalitássejtését olyan grafikonokhoz, amelyek végül lassan nőnek.

Ezen a ponton a matematikusok két csoportja sikeresen kezelte a sejtést különböző irányokból: gyors növekedésből és lassú növekedésből. Ez azonban jelentős hiányokat hagyott maga után. Egyrészt van egy közepes növekedési kategória, amelyre nem terjedt ki Easo és Hutchcroft technikája vagy Contreras, Martineau és Tassion bizonyítéka. Egy másik probléma az volt, hogy az érvek továbbra sem vonatkoztak a változó növekedési ütemű grafikonokra – csak azokra, amelyek gyorsak vagy lassúak maradtak. A Contreras, Martineau és Tassion argumentum tetszőleges gráfokra való alkalmazásához nem volt elég, hogy a geometria végül szelídnek tűnik, amikor kicsinyítjük, Easo kifejtette: „Szükségünk van rá, hogy most szelídnek tűnjön, közel a jelenlegi léptékhez.”

A semmi közepe

A köztes növekedés tranzitív grafikonjai nagyon titokzatosak. A matematikusok soha nem találtak példát tranzitív gráfra, amelynek növekedése ebbe a tartományba esik. Lehetséges, hogy nem is léteznek. A matematikusok azonban nem bizonyították, hogy nem léteznek, ezért Schramm lokalitássejtésének teljes bizonyítékának meg kell felelnie rájuk. A kihívást tovább növelte, hogy Easonak és Hutchcroftnak foglalkoznia kellett azokkal a grafikonokkal, amelyek csak rövid ideig mutathatnak közepes növekedést egy adott hosszúsági skálán, még akkor is, ha nagyításkor vagy kicsinyítéskor gyorsabban vagy lassabban nőnek.

Easo és Hutchcroft az elmúlt év nagy részét azzal töltötte, hogy eredményeiket olyan grafikonokra is kiterjesszék, amelyekre a korábbi módszerek egyike sem terjedt ki.

Először is módosították a 2018-as technikát, amelyet Hutchcroft a gyorsan növekvő grafikonokra alkalmazott, hogy olyan grafikonokon dolgozzanak, amelyek különböző léptékű növekedési szintet változtatnak. Ezután foglalkoztak a lassú növekedés ügyével egy 27 oldalas papír augusztusban megosztották a Contreras, Martineau és Tassion munkáit. Végül az októberi előnyomtatásukban egy másik érvet dolgoztak ki a véletlenszerű séták elméletével – olyan vonalak, amelyek véletlenszerűen mozognak a térben – a közbenső növekedés esetének kezelésére. A trichotómia befejeztével bebizonyították Schramm lokalitási sejtését.

„Mindent, amit tudtunk, fel kellett dobnunk a problémával” – mondta Hutchcroft.

A megoldás jobb betekintést ad a matematikusok számára abba, hogy mi történik a perkolációs küszöb felett, ahol a végtelen klaszter esélye 100%, illetve alatta, ahol az esély 0%. A matematikusokat azonban még mindig zavarja, hogy mi történik pontosan a legtöbb gráf küszöbénél, beleértve a háromdimenziós rácsot is. „Valószínűleg ez a leghíresebb, legalapvetőbb nyitott kérdés a perkolációs elméletben” – mondta Russell Lyons az Indiana Egyetemről.

A kétdimenziós rács azon kevés esetek egyike, amikor a matematikusok bebizonyították, hogy mi történik pontosan a küszöbön: nem képződnek végtelen klaszterek. És miután Grimmett és Marstrand bebizonyította a nagy födémekre vonatkozó lokális sejtés egy változatát, Grimmett és munkatársai megmutatták, hogy ha vízszintesen kettévágunk egy 3D-s rácsot, padlót hozunk létre, és a tárcsát pontosan a perkolációs küszöbre állítjuk, nem jelennek meg végtelen klaszterek. Eredményük arra utal, hogy a teljes háromdimenziós rácsnak, akárcsak a kétdimenziós megfelelőjének, nem lehet végtelen halmaza a perkolációs küszöbön.

1996-ban Benjamini és Schramm sejtik hogy annak az esélye, hogy egy végtelen klasztert közvetlenül a küszöbnél találunk, minden tranzitív gráf esetében nulla – éppúgy, mint a 2D rács vagy a félbevágott 3D rács esetében. Most, hogy a lokalitás sejtése megoldódott, talán egy kicsit közelebb kerül annak megértése, hogy mi történik közvetlenül az átmenet pontján.

Javítás: December 18, 2023
A 3-reguláris gráf kezdőcsomópontjának n hivatkozásán belüli csomópontok száma nagyjából 2-vel nőⁿ, nem pedig 3ⁿ ahogy ez a cikk eredetileg is megfogalmazta. A cikk javítva.

Quanta felméréssorozatot végez közönségünk jobb kiszolgálása érdekében. Vidd a miénket matematika olvasói felmérés és ingyenesen nyerhetsz Quanta árut.