« vorheriger Beitrag  · nächster Beitrag »

26.04.09 · 01:59 Uhr

Stabile Netzwerke - Neue Beispiele

Kategorie: Technik  ·  Kommentare: 3

Konstruktion stabiler Netzwerke mit Gruppentheorie.

Ein Netzwerk, zum Beispiel ein Telefonnetz, soll natürlich auch dann noch funktionieren, wenn einige Verbindungen ausfallen. Gleichzeitig möchte man diesen Effekt mit möglichst wenig Leitungen erreichen.

Einfaches Beispiel: man möchte 6 Punkte so verbinden, daß auch bei Ausfall von höchstens 2 Leitungen die Verbindungen noch funktionieren. Der Graph unten links ist natürlich nicht ausreichend, durch Ausfall zweier Leitungen wird der Zusammenhang zerstört. Einfach alle Punkte zu verbinden wäre (natürlich) ausreichend, aber mit 15 Leitungen viel zu aufwendig. Der rechte Graph stellt mit 9 Leitungen eine gute Lösung dar.

Die Stabilität eines Netzwerkes (mit Ecken E, Kanten K) wird durch die Cheeger-Zahl gemessen:

h:=min { #K(A,B)/min(#A,#B) : AUB=E }

wobei man also alle Zerlegungen der Eckenmenge E in zwei Teile A und B anschaut und #K(A,B) dann die Zahl der Verbindungskanten von A nach B ist.

Die Definition sieht vielleicht kompliziert aus, ist aber plausibel:
h ist klein, wenn man den Graphen so in zwei (annähernd gleich große) Teile zerlegen kann, daß es nur wenige Verbindungen zwischen den beiden Teilen gibt. Damit ist das "Netzwerk" aber sehr instabil, weil eine Störung dieser wenigen Verbindungen bereits den Zusammenhang zerstört.
(Die Graphen unten kann man z.B. durch Entfernen von 4 Kanten in Hälften mit 8-10 Stücken zerlegen, also ist h höchstens 4/8=0,5. Quelle: Mathworld)

Man sucht also systematische Methoden, um regelmäßige Graphen mit
- irgendeiner (großen) Zahl n von Ecken und
- irgendeiner festen Zahl k von Kanten an jeder Ecke
- mit nicht zu kleiner Cheeger-Zahl h zu konstruieren.
Solche Folgen von Graphen (bei denen die Cheeger-Zahl h größer ist als eine Kosntante ε) nennt man Expander-Folgen.

Eine Konstruktionsmethode für regelmäßige Graphen sind Cayley-Graphen¹ von Gruppen. Soweit ich weiß, bauen alle systematischen Konstruktionen von Expander-Folgen auf Cayley-Graphen (und damit auf Gruppentheorie) auf. Die historisch älteste Konstruktion einer Expander-Folge stammt von Margulis (1973) und benutzt tiefliegende Eigenschaften von Lie-Gruppen, speziell Eigenschaft T (dazu morgen noch ein 2. Beitrag). Seine Konstruktion wurde dann später verallgemeinert zu sogenannten Ramanujan-Graphen. (Der Name stammt daher, daß beim Beweis von h > ε die Ramanujan-Vermutung über Fourierkoeffizienten von Modulformen benutzt wird.)

Die Frage, wie weit sich diese Konstruktion verallgemeinern läßt, ist jetzt weitgehend beantwortet. Alexander Lubotzky hat in einer am Donnerstag herausgekommenen neuen Arbeit bewiesen, daß "endliche Gruppen von Lie-Typ" (d.h. Gruppen von Matrizen über endlichen Körpern), eventuell mit Ausnahme von Suzuki-Gruppen, solche Expander-Graphen liefern. (Das Ergebnis baut auf Arbeiten von Kassabov und Nikolov auf. Insbesondere hatte Kassabov in [1] schon bewiesen, daß für m > 2 und einen endlichen Körper F die Cayley-Graphen¹ der Gruppen
SL(m,F)
eine Expander-Folge sind. Lubotzky schreibt in der Einleitung: "Unlike the result mentioned previously whose proof used ingenious, but relatively elementary methods, the proof for PSL₂(q) will use some deep results from the theory of automorphic forms. In particular, it will appeal to Selberg λ₁ ≥ 3/16 Theorem and Drinfeld solution to the characteristic p Ramanujan conjecture.")

Lubotzkys Beweis für SL(2,F) gibt den letzten noch fehlenden Schritt im Beweis des bereits in [2] angekündigten Satzes:
Die Cayley-Graphen¹ von endlichen einfachen (nichtabelschen, nichtsuzukischen) Gruppen sind eine Expander-Folge.

¹: für geeignet gewählte Erzeugendensysteme der jeweiligen Gruppen

[1] Martin Kassabov, Universal lattices and unbounded rank expanders, Invent.
Math. 170 (2007), no. 2, 297-326.
[2] Martin Kassabov, Alexander Lubotzky and Nikolay Nikolov, Finite simple
groups as expanders, Proc. Natl. Acad. Sci. USA 103 (2006), no. 16, 6116-
6119.
[3] Alexander Lubotzky, Finite simple groups of Lie type as expanders, http://arxiv.org/abs/0904.3411
[4] Grigori Margulis, Explicit constructions of expanders (Russian), Problemy Peredači Informacii 9 (1973), no. 4, 71--80.

Kassabov, M. (2006). Finite simple groups as expanders Proceedings of the National Academy of Sciences, 103 (16), 6116-6119 DOI: 10.1073/pnas.0510337103

 

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

Tags: cayley-graph· endlich· expander· graph· gruppe· netzwerk