« vorheriger Beitrag  · nächster Beitrag »

13.02.11 · 17:12 Uhr

Zufall in der Topologie

Kategorie: Naturwissenschaften

Man fülle zufällig Dreiecke in ein vollständiges Gitter - wieviele Löcher bleiben übrig?

Im Januar-Heft des "Journal of the AMS" erscheint die Arbeit "The fundamental group of random 2-complexes" von Babson-Hoffman-Kahle.

Probabilistische Methoden erfreuen sich in der Mathematik zunehmender Beliebtheit. Die Grundidee ist: statt sich mit der Konstruktion einzelner Objekte mit speziellen Eigenschaften aufzuhalten, versucht man die Wahrscheinlichkeit zu berechnen, daß ein zufällig gewähltes Objekt diese Eigenschaft hat.

Schon lange angewandt wird dieses Konzept in der Graphentheorie. Dort betrachtet man u.a. das Modell der Erdös-Renyi-Zufallsgraphen: man gibt sich n Ecken vor und eine Wahrscheinlichkeit p mit der jede Kante existiert. Das Bild unten zeigt n=20 Ecken (zwischen denen also 190 mögliche Kanten existieren könnten), die Kanten werden mit Wahrscheinlichkeit p=0,1 eingezeichnet, d.h. eine "durchschnittliche Realisierung" sollte 19 Kanten haben.

Man kann dann die Wahrscheinlichkeiten dafür ausrechnen, daß es mehr als 19 Kanten gibt, oder die Wahrscheinlichkeit, daß der Graph zusammenhängend ist, oder die Wahrscheinlichkeit, daß es keine geschlossenen Kreise gibt etc.pp.

Erdös-Renyi haben in den 50er Jahren Folgen G(n,p(n)), von Zufallsgraphen betrachtet, wobei die Ecken-Zahl n alle natürlichen Zahlen durchläuft (also gegen Unendlich geht) und p(n) eine von n abhängende Wahrscheinlichkeit für die Existenz einer Kante ist.
Einen zusammenhängenden Graphen wird man wohl eher dann bekommen, wenn es viele Kanten gibt, wenn also p nicht zu klein ist. Tatsächlich haben Erdös-Renyi 1959 bewiesen, daß für p(n)>(1+ε)log(n)/n die Wahrscheinlichkeit, einen zusammenhängenden Graphen zu bekommen, gegen 1 konvergiert (für n gegen Unendlich), während für p(n)<(1-ε)log(n)/n die Wahrscheinlichkeit für einen zusammenhängenden Graphen gegen 0 konvergiert.

Was ist die 2-dimensionale Verallgemeinerung des Zufallsgraphen-Modells? ,
Man nimmt wieder n Ecken, man nimmt alle Kanten zwischen diesen Ecken, d.h. man nimmt den vollständigen Graphen

und zu je drei Ecken setzt man mit Wahrscheinlichkeit p das Dreieck zwischen diesen Ecken ein. (Das Bild unten zeigt nur die gewählten Dreiecke und nicht die freien Kanten, die man ja zwischen je zwei Ecken hat.)

Es ist klar, daß eine solche zufällige Fläche zusammenhängend ist: je zwei Ecken sind durch eine Kante verbunden. (Allgemeiner ist in Arbeiten von Linial, Meshulam, Wallach die Z₂-Homologie solcher zufälliger Komplexe berechnet worden.)

In der Arbeit von Babson-Hoffman-Kahle wird nun die Fundamentalgruppe π₁Y solcher zufälliger 2-Komplexe Y untersucht, also im Prinzip die Frage, ob es geschlossene Kanten-Wege gibt, die nicht im Rand einer Vereinigung von Dreiecken liegen.

Anschaulich ist natürlich klar, daß die Fundamentalgruppe π₁Y für großes p immer einfacher werden sollte: je mehr Dreiecke man einfüllt, desto mehr Kanten-Wege sind Rand einer Vereinigung von Dreiecken.

Tatsächlich wird in der Arbeit bewiesen, daß für p(n)>(3+ε)log(n)/n die Wahrscheinlichkeit, einen 2-Komplex Y mit π₁Y=0 zu bekommen, gegen 1 konvergiert (für n gegen Unendlich).

Beweisskizze: für jedes Ecken-Paar (a,b) gilt (mit Wahrscheinlichkeit -->1 für n gegen Unendlich):
- es gibt eine Ecke d, so daß (a,b,d) ein Dreieck in Y bilden
- der Durchschnitt der Links lk(a) und lk(b) ist zusammenhängend.
(Die 2.Bedingung gilt, weil der Durchschnitt der beiden Links ein Zufallsgraph mit n-2 Ecken ist, auf den man den oben erwähnten Satz von Erdös-Renyi anwenden kann.)
Aus diesen beiden Bedingungen folgt dann leicht, daß auch für jede andere Ecke c der Kantenzug (a,b,c) eine Vereinigung von Dreiecken berandet, nämlich die Vereinigung aus dem Dreieck (a,b,c) und aus den Dreiecken (a,e_i,e_i+1), (b,e_i,e_i+1), wobei c,e₁,...,e_i,e_i+1,...,d ein Kantenzug von c nach d im (zusammenhängenden) Durchschnitt von lk(a) und lk(b) ist.
QED

Was passiert, wenn die Dreiecke mit geringerer Wahrscheinlichkeit eingefüllt werden? Kann man etwas über die Fundamentalgruppen aussagen, die man dann erhält?

Plausibel wäre, daß man meist hyperbolische Gruppen erhält. Aus der Topologie weiß man ja, daß die meisten Flächen hyperbolisch sind (nämlich alle geschlossenen Flächen außer Sphäre, Torus, projektive Ebene, Kleinsche Flasche), ein ähnliches Ergebnis gilt für Flächen mit Rand. (Und ganz allgemein weiß man, daß die meisten Gruppen hyperbolisch sind.) Aber es ist natürlich a priori nicht klar, ob man beim gewählten Wahrscheinlichkeitsmodell nicht vielleicht häufiger Sphären und Tori als hyperbolische Flächen bekommen könnte.

Jedenfalls beantworten Babson-Hoffman-Kahle auch diese Frage: sie beweisen, daß für p(n) ≤ Cn^-0,5-ε die Wahrscheinlichkeit, einen 2-Komplex Y mit (nichttrivialer) hyperbolischer Fundamentalgruppe π₁Y=0 zu bekommen, gegen 1 konvergiert (für n gegen Unendlich).

Beweisskizze:
Für einen 2-Komplex Z und i=0,1,2 bezeichne f_i(Z) die Anzahl der i-Simplizes in Z. Ein 2-Komplex mit Eckenmenge {1,...,n} heißt (ε,3)-zulässig, wenn jeder die Ecken {1,2,3} enthaltende Unterkomplex Z die Ungleichung f₀(Z)-3 ≥ (0,5+ε)f₂(Z) erfüllt. Ein 2-Komplex mit Eckenmenge {1,...,n} heißt (ε,m,3)-karg, wenn jeder Unterkomplex mit ≤ m Ecken (ε,3)-zulässig ist.

Eine einfache Rechnung zeigt, daß für p(n) ≤ Cn^-0,5-ε die Wahrscheinlichkeit dafür, daß ein zufälliger 2-Komplex (in dem die Dreiecke mit Wahrscheinlichkeit p(n) eingefüllt wurden) (ε,m,3)-karg ist, gegen 1 konvergiert (für n gegen Unendlich).

Babson-Hoffman-Kahle beweisen dann zunächst einen topologischen Satz, der auch von unabhängigem Interesse sein dürfte: jeder (ε,3)-zulässige (endliche) 2-dimensionale Komplex ist homotopie-äquivalent zu einer disjunkten Vereinigung von 1-Punkt-Vereinigungen von Kreisen, 2-Sphären und projektiven Ebenen. Insbesondere ist die Fundamentalgruppe ein freies Produkt aus Z's und Z/2Z's und deshalb hyperbolisch.

Gromov hat bewiesen, daß eine Gruppe Γ dann und nur dann hyperbolisch ist, wenn jeder endliche Simplizialkomplex X mit Π₁X=Γ eine lineare isoperimetrische Ungleichung erfüllt.

Insbesondere, wenn Y ein (ε,m,3)-karger 2-Komplex auf den Ecken {1,...,n} ist und Z ein Unterkomplex, der die Ecken {1,2,3} enthält und ≤ m Ecken hat, dann ist Z (ε,3)-zulässig, hat also hyperbolische Fundamentalgruppe, erfüllt also eine lineare isoperimetrische Ungleichung.

Es gibt aber ein Lokal-Global-Prinzip für isoperimetrische Ungleichungen, aus dem man dann die lineare isoperimetrische Ungleichung (und damit die Hyperbolizität der Fundamentalgruppe) auch für Y selbst folgern kann. (Das beweist die Hyperbolizität der Fundamentalgruppe, aber noch nicht π₁Y ≠ 0, denn auch die triviale Gruppe wäre ja hyperbolisch.)

Aus der linearen isoperimetrischen Ungleichung und der Definition von (ε,m,3)-Kargheit kann man schließlich folgern, daß die Wahrscheinlichkeit dafür, daß der geschlossene Weg der Länge 3 aus den Verbindungskanten von {1,2,3} nicht 0-homotop (also nicht Rand einer Verinigung von Dreiecken) ist, gegen 1 konvergiert (für n gegen Unendlich). Insbesondere konvergiert die Wahrscheinlichkeit für π₁Y ≠ 0 gegen 1.
QED

Eric Babson, Christopher Hoffman, & Matthew Kahle (2010). The fundamental group of random 2-complexes J. Amer. Math. Soc. 24 (2011), 1-28 arXiv: 1010.6043v1

 

Autor: Thilo· 0 Kommentare· Permalink· Trackback-URL

Tags: Babson· Erdös· Fundamentalgruppe· Graph· Hoffman· hyperbolisch· Kahle· Komplex· Renyi· Wahrscheinlichkeit· Zufall