Stabile Netzwerke durch hyperbolische Geometrie.

Letzte Woche hatten wir über Expander-Graphen (“stabile Netzwerke”) geschrieben – Graphen, bei denen es nicht möglich ist, sie durch Entfernen weniger Kanten in zwei annähernd gleich große Komponenten zu zerlegen.

Wenn man Expander konstruieren will, braucht man zunächst eine (berechenbare) Zahl, mit der man die “Expansion” eines Graphen messen kann – diese Zahl ist der (zweite) Eigenwert des Laplace-Operators.

Laplace-Operator auf Graphen

Ein Graph besteht aus Ecken und Kanten. Zwei Ecken sind entweder durch eine Kante verbunden oder nicht. Wenn zwei Ecken durch eine Kante verbunden sind, sagt man, sie sind “adjazent”.

Die Adjazenzmatrix hat als Eintrag an der Stelle (i,j) eine 1 (wenn die i-te und j-te Ecke verbunden sind) oder eine 0 (wenn die Ecken nicht verbunden sind).
Die Adjazenz-Matrix des oben abgebildeten Graphen (die 1.Ecke soll mit sich selbst verbunden sein):

Statt der Adjazenz-Matrix benutzt man oft die Laplace-Matrix L, das ist die Differenz L=D-A, wobei D die Diagonalmatrix diag(grad(v₁), … ,grad(v_n)) ist. (Der Grad der Ecke v_i ist die Anzahl der von v_i ausgehenden Kanten.)
Die Laplace-Matrix des oben abgebildeten Graphen:

Der Laplace-Operator L (oder eigentlich LD^-1) beschreibt die Diffusion auf dem Graphen.
Das heißt: die Wahrscheinlichkeit, daß eine Irrfahrt, die in der Ecke v₁ beginnt, zum Zeitpunkt k in der Ecke v_i landet, ist gerade der i-te Eintrag von (LD^-1)^k(1,0,…,0).

Expander und Laplace-Operator

Expander sind Graphen, bei denen es nicht möglich ist, sie durch Entfernen weniger Kanten in zwei annähernd gleich große Komponenten zu zerlegen.
Mathematisch läßt sich das über die Cheeger-Zahl h ausdrücken, diese soll größer sein als ein konstantes ε. (Die genaue Definition der Cheeger-Zahl hatten wir hier schon mal.)

Statt der (schwer zu berechnenden) Cheeger-Zahl berechnet man lieber die Eigenwerte des Laplace-Operators.

Für einen “regulären” Graphen (d.h. von jeder Ecke geht die gleich Zahl d von Kanten aus), ist offensicthlich d ein Eigenwert der Adjazenz-Matrix, zum Eigenvektor (1,1,…,1). Also ist 0 ein Eigenwert des Laplace-Operators.

Alle anderen Eigenwerte sind positiv. Den (nach 0) kleinsten Eigenwert des Laplace-Operators nennt man λ.

λ hängt eng mit der Cheeger-Zahl h zusammen. Insbesondere ist eine Folge von Graphen genau dann eine Expander-Folge, wenn der Eigenwert λ größer als ein konstantes ε ist.
Genauer: die Cheeger-Ungleichung besagt λ ≥ h²/4, und umgekehrt hat Buser eine obere Schranke für λ in Abhängigkeit von h bewiesen.

Graphen und Gruppen

Eigentlich sollte es nicht schwer sein, Expander-Graphen zu finden. Denn ein zufällig gewählter Graph hat mit 100%-iger Wahrscheinlichkeit einen ziemlich großen Eigenwert λ.
(Genauer: für einen zufällig gewählten regulären Graphen, bei dem von jeder Ecke d Kanten ausgehen, ist mit fast 100%-iger Wahrscheinlichkeit λ mindestens d minus 2 mal die Wurzel aus d-1 minus ε. Das ist “Alon’s second eigenvalue conjecture”, die vor einigen Jahren von Joel Friedman bewiesen wurde.)

Aber wie bekommt man konkrete Beispiele?

Viele sehr regelmäßige Graphen bekommt man als Cayleygraphen von Gruppen – deren Konstruktion hatten wir in TvF 83 beschrieben.

Graphen und Flächen

Zufällig gewählte Graphen sind mit 100%-iger Wahrscheinlichkeit Expander. Auch wenn man speziell nur Cayley-Graphen von Gruppen nimmt, sind diese mit 100%-iger Wahrscheinlichkeit Expander. (Jedenfalls für eine bestimmte Definition von “Zufalls-Gruppen”, das sogenannte “Dichtemodell mit d>1/3”.)

Trotzdem braucht man recht komplizierte Methoden, um Expander als Cayleygraphen zu konstruieren. Benutzt wird z.B. die Geometrie von hyperbolischen Flächen oder die Eigenschaften von Modulformen.

Mit hyperbolischer Geometrie kann man beweisen, daß die Cayley-Graphen von SL(2,Z/nZ) Expander sind. (Diese Gruppe besteht aus den 2×2-Matrizen mit Determinante 1, deren Einträge Restklassen modulo n sind.)

Der Zusammenhang mit der Geometrie hyperbolischer Flächen kommt wie folgt:

wenn man eine (diskrete) Gruppe von Isometrien der hyperbolischen Ebene hat, dann ist der “Quotient” eine hyperbolische Fläche.

====>

Quelle: Mathworld

In TvF 90 hatten wir mal die Gruppe SL(2,Z). (Diese Gruppe entspricht keiner “richtigen” hyperbolischen Fläche, sondern einer hyperbolischen Fläche mit “Kegelsingularitäten”, siehe TvF 91. Das spielt hier aber keine Rolle.)

Spezielle Untergruppen von SL(2,Z) sind die “Kongruenzgruppen” Γ_n, d.i. die 2×2-Matrizen mit ganzzahligen Einträgen, die modulo n kongruent zur Einheitsmatrix sind. (Für jedes n bekommt man eine solche Gruppe Γ_n.)

(Auch diese Gruppen entsprechen keinen “richtigen” hyperbolischen Flächen, sondern hyperbolischen Flächen mit “Kegelsingularitäten”.) Man hat SL(2,Z)/Γ_n=SL(2,Z/nZ).

Atle Selberg hatte 1965 vermutet, daß für die Gruppen SL(2,Z/nZ) der Eigenwert λ mindestens 1/4 ist. Diese Vermutung ist zwar noch offen, Selberg konnte aber jedenfalls beweisen, daß λ > 3/16.

Der Beweis geht i.w. wie folgt: man schaut sich die hyperbolischen Flächen zu den Kongruenzgruppen Γ_n an. Diese sind eine Überlagerung der hyperbolischen Fläche zu SL(2,Z), die Symmetriegruppe der Überlagerung ist SL(2,Z/nZ). Insbesondere kann man den Cayley-Graphen von SL(2,Z/nZ) auf naheliegende Weise in die Fläche zu Γ_n einzeichen. Und es läßt sich dann beweisen, daß die Eigenwerte des Laplace-Operators des Graphen eng mit den Eigenwerten des “üblichen” (analytisch definierten) Laplace-Operators auf der hyperbolischen Fläche zusammenhängen. Und für den Laplace-Operator der hyperbolischen Fläche kann man die Ungleichung λ > 3/16 mit Hilfe hyperbolischer Geometrie beweisen.

Die Cayleygraphen zu SL(2,Z/nZ) sind also Expander.

Teil 1, Teil 2, Teil 3, Teil 4, Teil 5, Teil 6, Teil 7 , Teil 8, Teil 9 , Teil 10 ,Teil 11, Teil 12, Teil 13, Teil 14, Teil 15, Teil 16, Teil 17, Teil 18, Teil 19, Teil 20, Teil 21, Teil 22, Teil 23, Teil 24, Teil 25, Teil 26, Teil 27, Teil 28, Teil 29, Teil 30, Teil 31, Teil 32, Teil 33, Teil 34, Teil 35, Teil 36, Teil 37, Teil 38, Teil 39, Teil 40, Teil 41, Teil 42, Teil 43, Teil 44, Teil 45, Teil 46, Teil 47, Teil 48, Teil 49, Teil 50, Teil 51, Teil 52, Teil 53, Teil 54, Teil 55, Teil 56, Teil 57, Teil 58, Teil 59, Teil 60, Teil 61, Teil 62, Teil 63, Teil 64, Teil 65, Teil 66, Teil 67, Teil 68, Teil 69, Teil 70, Teil 71, Teil 72, Teil 73, Teil 74, Teil 75, Teil 76, Teil 77, Teil 78, Teil 79, Teil 80, Teil 81, Teil 82, Teil 83, Teil 84, Teil 85, Teil 86, Teil 87, Teil 88, Teil 89, Teil 90, Teil 91, Teil 92, Teil 93, Teil 94, Teil 95, Teil 96, Teil 97, Teil 98, Teil 99, Teil 100, Teil 101