Eine Nahaufnahme zeigt den „Schmelzpunkt“ eines unendlichen Graphen | Quanta-Magazin

Im Jahr 2008 starb der Mathematiker Oded Schramm bei einem Wanderunfall in den Cascade Mountains etwa 50 Meilen östlich von Seattle. Obwohl er erst 46 Jahre alt war, hatte er völlig neue Bereiche der Mathematik aufgebaut.

„Er war ein fantastischer Mathematiker“, sagte er Itai Benjamini, ein Mathematiker am Weizmann Institute of Science und Schramms Freund und Mitarbeiter. „Extrem kreativ, extrem elegant, extrem originell.“

Die von ihm gestellten Fragen verschieben immer noch die Grenzen der Wahrscheinlichkeitstheorie und der statistischen Physik. Viele dieser Fragen betreffen mathematische Strukturen, die einen Phasenübergang haben – eine plötzliche makroskopische Veränderung, wie das Schmelzen von Eis zu Wasser. So wie verschiedene Materialien unterschiedliche Schmelzpunkte haben, variieren auch die Phasenübergänge mathematischer Strukturen.

Schramm vermutete, dass der Phasenübergang in einem Prozess namens Perkolation für viele wichtige mathematische Strukturen allein durch die Verwendung einer Nahansicht des Systems – der sogenannten lokalen Perspektive – abgeschätzt werden kann. Wenn Sie ganz herauszoomen und das Ganze betrachten, ändert sich die Berechnung nicht wesentlich. In den letzten 15 Jahren haben Mathematiker an kleinen Teilen der Vermutung herumgehackt, aber bis jetzt ist es ihnen nicht gelungen, sie vollständig zu lösen.

In einer Vorabdruck veröffentlicht im Oktober, Tom Hutchcroft des California Institute of Technology und sein Doktorand Philip Easo bewies Schramms Lokalitätsvermutung. Ihr Beweis stützt sich auf wichtige Ideen aus der Wahrscheinlichkeitstheorie und anderen Bereichen der Mathematik, die sie auf clevere Weise kombinierten.

„Es ist ein bemerkenswertes Papier. Es ist eine Anhäufung langer Arbeit“, sagte Benjamini.

Unendliche Cluster

Das Wort „Perkolation“ bezog sich ursprünglich auf die Bewegung von Flüssigkeit durch ein poröses Medium, beispielsweise Wasser, das durch Kaffeesatz fließt, oder Öl, das durch Risse in einem Gestein sickert.

1957 entwickelten die Mathematiker Simon Ralph Broadbent und John Michael Hammersley ein mathematisches Modell dieses physikalischen Prozesses. In den darauffolgenden Jahrzehnten ist dieses Modell zu einem eigenständigen Forschungsgegenstand geworden. Mathematiker untersuchen die Perkolation, weil sie ein wichtiges Gleichgewicht schafft: Der Aufbau ist einfach, weist jedoch komplexe und rätselhafte Merkmale auf.

„Es ist eine Art kanonisches Modell für Mathematiker“, sagte Hutchcroft. „Man kann sich Dinge visuell vorstellen. Das macht die Zusammenarbeit wirklich angenehm.“

Die Perkolation beginnt mit einem Diagramm, das eine Sammlung von Eckpunkten (Punkten) ist, die durch Kanten (Linien) verbunden werden können. Eines der einfachsten Beispiele ist ein quadratisches Gitter, bei dem Scheitelpunkte aneinandergereiht sind, um die Ecken von Quadraten zu bilden, und Kanten, die einige von ihnen verbinden.

Kurz vor seinem Tod vermutete Schramm, dass der Satz von Grimmett und Marstrand verallgemeinert werden könne. Er glaubte, dass die Perkolationsschwelle vollständig durch die Nahaufnahme oder „mikroskopische“ Perspektive für eine große Klasse von Graphen, die als transitive Graphen bekannt sind, bestimmt wird.

Im Jahr 2009, Benjamini, Asaf Nachmias und Yuval Peres erwies sich Schramms Lokalitätsvermutung, wie sie heute genannt wird, für einen bestimmten Typ eines transitiven Graphen, der einem Baum ähnelt. Schramm hatte jedoch postuliert, dass dies für alle transitiven Graphen gelten würde (mit Ausnahme für eindimensionale Graphen).

In einem transitiven Graphen sehen alle Eckpunkte ähnlich aus. Ein Beispiel ist ein zweidimensionales Gitter. Wenn Sie zwei beliebige Scheitelpunkte auswählen, können Sie immer eine Symmetrie finden, die einen Scheitelpunkt zum anderen verschiebt.

Diese Beziehung gilt für jeden transitiven Graphen. Aufgrund dieser Symmetrien sehen zwei gleichgroße Felder eines transitiven Diagramms gleich aus, wenn Sie hineinzoomen und sie betrachten. Aus diesem Grund glaubte Schramm, dass die Nahperspektive ausreichte, um Mathematikern die Berechnung der Perkolationsschwelle für alle transitiven Graphen zu ermöglichen.

Transitive Graphen können viele Formen und Gestalten annehmen. Sie können ein einfaches Gitter sein, das aus Quadraten, Dreiecken, Sechsecken oder einer anderen Form besteht. Oder sie können ein komplexeres Objekt bilden, wie einen „3-regelmäßigen Baum“, bei dem ein zentraler Punkt mit drei Scheitelpunkten verbunden ist und jeder Scheitelpunkt sich dann verzweigt, um bis ins Unendliche zwei neue zu erzeugen, deren erste Schritte hier zu sehen sind:

Die Vielfalt der transitiven Graphen trug dazu bei, dass es schwierig war, Schramms Lokalitätsvermutung zu beweisen. In den 15 Jahren zwischen Schramms Vermutung und dem Beweis von Easo und Hutchcroft haben verschiedene Gruppen von Mathematikern die Vermutung für bestimmte Arten von Graphen bewiesen, aber ihre Ideen haben sich nie auf den allgemeinen Fall ausgeweitet.

„Der Raum aller möglichen Geometrien ist einfach riesig und es lauern immer seltsame Dinge“, sagte Hutchcroft.

Das Objektiv erweitern

Easo und Hutchcroft suchten zunächst nicht nach einer Lösung für Schramms Lokalitätsvermutung, die für unendliche Graphen gilt. Stattdessen untersuchten sie die Perkolation auf endlichen Graphen. Aber sie hatten eine Idee, die ihre Aufmerksamkeit plötzlich auf die Vermutung lenkte.

„Wir haben uns dieses neue Tool ausgedacht und dachten: Oh, das scheint etwas zu sein, das hilfreich sein könnte, um die Lokalität anzugreifen“, sagte Easo.

Um die Vermutung zu beweisen, mussten sie zeigen, dass die mikroskopische Perspektive eine genaue Momentaufnahme der Perkolationsschwelle liefert. Wenn Sie nur einen Teil eines Diagramms betrachten und einen großen verbundenen Cluster beobachten, können Sie davon ausgehen, dass das Diagramm einen unendlichen Cluster aufweist und daher über dem Perkolationsschwellenwert liegt. Easo und Hutchcroft machten sich daran, es zu beweisen.

Sie verließen sich auf eine Technik, die man sich als „Erweiterung der Linse“ vorstellen kann. Beginnen Sie an einem einzelnen Scheitelpunkt. Zoomen Sie dann heraus, um alle Scheitelpunkte anzuzeigen, die im Originaldiagramm nur eine Kante entfernt sind. Auf dem quadratischen Raster sehen Sie nun insgesamt fünf Eckpunkte. Erweitern Sie die Linse erneut, um alle Scheitelpunkte innerhalb eines Abstands von zwei Kanten und dann eines Abstands von drei Kanten, vier Kanten usw. zu sehen.

Easo und Hutchcroft stellen den Regler ein, der bestimmt, wie viele Verbindungen sich in der Nähe der Stelle befinden, an der sie eine große Ansammlung gesehen haben. Dann erweiterten sie die Linse und beobachteten, wie sich immer mehr Kanten in ihrem großen Cluster sammelten. Dabei mussten sie die Wahrscheinlichkeit erhöhen, dass Links vorhanden sind, was es einfacher macht zu zeigen, dass der Graph eine große Zusammenhangskomponente hat. Das ist ein heikler Balanceakt. Sie mussten das Sichtfeld schnell genug erweitern und Links langsam genug hinzufügen, um die gesamte unendliche Grafik sichtbar zu machen, ohne die Position des Zifferblatts dramatisch zu ändern.

Sie konnten zeigen, dass große Cluster schneller wachsen als kleinere, sodass, wie Easo es ausdrückte, „Ihr Cluster immer schneller wächst, je größer er wird, genau wie wenn Sie einen Schneeball rollen.“

Beim quadratischen Gitter wächst die Scheitelpunktzahl relativ langsam. Es entspricht ungefähr der Breite Ihres Objektivs im Quadrat. Nach 10 Schritten finden Sie etwa 100 Eckpunkte. Aber ein 3-regulärer Baum wächst exponentiell schneller – ungefähr 2 hoch hoch Ihrer Linsenweite. Nach 10 Schritten sehen Sie etwa 1,024 Eckpunkte. Die Abbildung unten zeigt, dass der 3-regelmäßige Baum nach nur sieben Schritten viel größer ist, obwohl das quadratische Gitter zunächst mehr Eckpunkte hat. Im Allgemeinen können Diagramme in verschiedenen Maßstäben unterschiedliche Wachstumsraten aufweisen – sie beginnen möglicherweise schnell und verlangsamen sich dann.

Im Jahr 2018, Hutchcroft habe eine ähnliche Idee verwendet um die Lokalitätsvermutung für schnell wachsende Graphen wie den 3-regulären Baum zu beweisen. Aber es funktionierte nicht bei langsam wachsenden Diagrammen wie dem quadratischen Gitter oder bei Diagrammen, die mit mittlerer Geschwindigkeit wachsen und weder die mathematischen Kriterien für schnelles Wachstum noch die für langsames Wachstum erfüllten.

„Dann wird es drei Jahre lang wirklich frustrierend“, sagte Hutchcroft.

Struktur versus Expansion

Für Diagramme, die Wachstumsraten in verschiedenen Maßstäben mischen, müssen Sie verschiedene Techniken verwenden.

Eine sehr hilfreiche Tatsache ist, wie Easo erklärte: „Wenn eine Grafik in einem bestimmten Maßstab langsam wächst, bleibt sie hängen.“ In größeren Maßstäben wird es weiterhin langsam wachsen. Da langsam wachsende Graphen eine zusätzliche Struktur haben, die durch einen Zweig der Mathematik namens Gruppentheorie bestimmt wird, war auch bekannt, dass langsam wachsende Graphen eine mathematisch harmlose Geometrie anzeigen, wenn man weit genug herauszoomt.

Im Jahr 2021 arbeitete Sébastien Martineau von der Universität Sorbonne in Paris mit Daniel Contreras und Vincent Tassion der ETH Zürich, konnte diese Liegenschaft nutzen beweisen Sie Schramms Lokalitätsvermutung für Diagramme, die schließlich langsam wachsen.

Zu diesem Zeitpunkt hatten die beiden Gruppen von Mathematikern die Vermutung aus unterschiedlichen Richtungen erfolgreich angegangen: schnelles Wachstum und langsames Wachstum. Dies hinterließ jedoch erhebliche Lücken. Zum einen gibt es eine mittlere Wachstumskategorie, die weder durch die Technik von Easo und Hutchcroft noch durch den Beweis von Contreras, Martineau und Tassion abgedeckt wurde. Ein weiteres Problem bestand darin, dass die Argumente immer noch nicht auf Diagramme mit sich ändernden Wachstumsraten zutrafen – nur auf solche, die schnell oder langsam blieben. Damit das Argument von Contreras, Martineau und Tassion auf beliebige Diagramme angewendet werden konnte, reichte es nicht aus, dass die Geometrie beim Herauszoomen letztendlich harmlos aussieht, erklärte Easo: „Wir brauchen, dass sie jetzt, in der Nähe des aktuellen Maßstabs, harmlos aussieht.“

Mitten im Nirgendwo

Transitive Graphen des Zwischenwachstums sind sehr mysteriös. Mathematiker haben noch nie ein Beispiel für einen transitiven Graphen gefunden, dessen Wachstum in diesem Bereich liegt. Es ist möglich, dass sie gar nicht existieren. Aber Mathematiker haben nicht bewiesen, dass sie nicht existieren, daher muss sich jeder vollständige Beweis von Schramms Lokalitätsvermutung mit ihnen befassen. Zusätzlich zur Herausforderung mussten sich Easo und Hutchcroft mit Diagrammen befassen, die auf einer bestimmten Längenskala möglicherweise nur kurzzeitig ein mittleres Wachstum aufweisen, selbst wenn sie beim Vergrößern oder Verkleinern schneller oder langsamer wachsen.

Easo und Hutchcroft haben einen Großteil des vergangenen Jahres damit verbracht, ihre Ergebnisse zu erweitern, um sie auf Diagramme anzuwenden, die von keiner der früheren Methoden abgedeckt wurden.

Zunächst modifizierten sie die Technik von 2018, die Hutchcroft auf schnell wachsende Diagramme angewendet hatte, um an Diagrammen zu arbeiten, die das Wachstumsniveau in verschiedenen Maßstäben ändern. Anschließend befassten sie sich mit dem Fall des langsamen Wachstums ein 27-seitiges Papier Sie teilten im August mit, dass sie die Arbeit an Contreras, Martineau und Tassion erweiterten. Schließlich entwickelten sie in ihrem Vorabdruck vom Oktober ein weiteres Argument unter Verwendung der Theorie der Zufallswanderungen – Linien, die sich zufällig durch den Raum bewegen –, um den Fall des Zwischenwachstums zu behandeln. Nachdem die Trichotomie abgeschlossen war, hatten sie Schramms Lokalitätsvermutung bewiesen.

„Wir mussten alles, was wir wussten, gegen das Problem einsetzen“, sagte Hutchcroft.

Die Lösung gibt Mathematikern einen besseren Einblick in das, was oberhalb der Perkolationsschwelle passiert, wo die Wahrscheinlichkeit eines unendlichen Clusters 100 % beträgt, und darunter, wo die Wahrscheinlichkeit 0 % beträgt. Aber Mathematiker sind immer noch ratlos darüber, was bei den meisten Graphen, einschließlich des dreidimensionalen Gitters, genau an der Schwelle passiert. „Das ist wahrscheinlich die berühmteste und grundlegendste offene Frage in der Perkolationstheorie“, sagte er Russel Lyon der Indiana University.

Das zweidimensionale Gitter ist einer der wenigen Fälle, in denen Mathematiker bewiesen haben, was genau an der Schwelle passiert: Es bilden sich keine unendlichen Cluster. Und nachdem Grimmett und Marstrand eine Version der Lokalitätsvermutung für große Platten bewiesen hatten, zeigten Grimmett und Mitarbeiter, dass keine unendlichen Cluster erscheinen, wenn man ein 3D-Gitter horizontal in zwei Hälften schneidet, um einen Boden zu schaffen, und das Zifferblatt genau auf die Versickerungsschwelle einstellt. Ihr Ergebnis deutet darauf hin, dass das vollständige dreidimensionale Gitter, wie sein zweidimensionales Gegenstück, an der Perkolationsschwelle möglicherweise keinen unendlichen Cluster aufweist.

1996 Benjamini und Schramm vermutet dass die Wahrscheinlichkeit, direkt an der Schwelle einen unendlichen Cluster zu finden, für alle transitiven Graphen Null ist – genauso wie für das 2D-Gitter oder das in zwei Hälften geschnittene 3D-Gitter. Nachdem die Lokalitätsvermutung nun geklärt ist, könnte das Verständnis dafür, was direkt am Übergangspunkt passiert, etwas näher sein.

Korrektur: 18. Dezember 2023
Die Anzahl der Knoten innerhalb von n Links eines Startknotens in einem 3-regulären Graphen wächst auf ungefähr 2ⁿnicht 3ⁿ wie in diesem Artikel ursprünglich angegeben. Der Artikel wurde korrigiert.

Wie viel führt eine Reihe von Umfragen durch, um unser Publikum besser zu bedienen. Nimm unser Leserbefragung Mathematik und Sie nehmen an der kostenlosen Verlosung teil Wie viel Merch.