Expander-Graph

In der Mathematik sind Expander-Graphen Familien von Graphen, die gleichzeitig dünn und hochzusammenhängend sind und sehr gute Stabilitätseigenschaften haben, sich also nicht durch Entfernen relativ weniger Kanten in mehrere Zusammenhangskomponenten zerlegen lassen. Anschaulich heißt das, dass jede „kleine“ Teilmenge von Knoten eine relativ „große“ Nachbarschaft hat.

Definitionen

Ein Graph $X=(E,K)$ ist ein $\varepsilon$-Expander, wenn seine Cheeger-Konstante die Ungleichung

$h(X)\geq \varepsilon$

erfüllt.

Man spricht von einer Familie von Expander-Graphen, wenn

• es ein $\varepsilon >0$ gibt, so dass alle Graphen der Familie $\varepsilon$-Expander sind,

und wenn weiterhin

• die Knotenzahl der Graphen gegen Unendlich geht (für jedes $N\in \mathbb {N}$ gibt es in der Familie nur endlich viele Graphen der Familie mit weniger als $N$ Knoten)

und

• es eine gleichmäßige obere Schranke $v$ für den Knotengrad der Graphen gibt.

Wegen der Cheeger-Buser-Ungleichung ist die erste Bedingung äquivalent zu der Forderung, dass es ein $\varepsilon ^{\prime }>0$ gibt, so dass für alle Graphen der Familie der zweitkleinste Eigenwert $\lambda _{1}$ der Laplace-Matrix die Ungleichung

$\lambda _{1}(X)\geq \varepsilon ^{\prime }$

erfüllt.

Der Name „Expander-Graph“ erklärt sich durch die folgende Eigenschaft von $\varepsilon$-Expandern mit oberer Schranke $v$ für den Knotengrad: für einen Knoten $x$ ist die Anzahl der Knoten vom Abstand $\leq n$ mindestens $\min \left({\frac {\mid E\mid }{2}},\left(1+{\frac {\varepsilon }{v}}\right)^{n}\right)$.

Beispiele

• Die Cayley-Graphen von $SL(2,\mathbb {Z} /n\mathbb {Z} )$ sind Expander, denn für sie gilt $\lambda _{1}>{\frac {3}{16}}$. Nach der noch unbewiesenen Selberg-Vermutung sollte sogar stets $\lambda _{1}\geq {\frac {1}{4}}$ sein.

• Ramanujan-Graphen haben optimale Expander-Eigenschaften.

• Der Petersen-Graph ist ein Ramanujan-Graph.

• Lubotzky-Philips-Sarnak konstruieren Familien von Ramanujan-Graphen als Quotienten p-adischer symmetrischer Räume $PGL(2,\mathbb {Q} _{p})/PGL(2,\mathbb {Z} _{p})$ unter gewissen Gruppenwirkungen.

• Es gibt verschiedene Argumente, dass bestimmte Klassen von Zufallsgraphen mit positiver Wahrscheinlichkeit oder sogar mit Wahrscheinlichkeit $1$ Expander-Graphen oder sogar Ramanujan-Graphen sind. Historisch wurde die erste solche Klasse 1967 von Kolmogorov-Barzdins beschrieben.

Literatur

• Alexander Lubotzky: Discrete groups, expanding graphs and invariant measures. With an appendix by Jonathan D. Rogawski. Progress in Mathematics, 125. Birkhäuser Verlag, Basel, 1994. ISBN 3-7643-5075-X
• Shlomo Hoory, Nathan Linial, Avi Wigderson: Expander Graphs and their Applications, Bulletin of the AMS, Band 43, 2006, S. 439–561, Online

Weblinks

• E. Kowalski: Expander Graphs
• N. Linial, A. Wigderson: Expander Graphs and their applications