Expander-Graph

In d​er Mathematik s​ind Expander-Graphen Familien v​on Graphen, d​ie gleichzeitig dünn u​nd hochzusammenhängend s​ind und s​ehr gute Stabilitätseigenschaften haben, s​ich also n​icht durch Entfernen relativ weniger Kanten i​n mehrere Zusammenhangskomponenten zerlegen lassen. Anschaulich heißt das, d​ass jede „kleine“ Teilmenge v​on Knoten e​ine relativ „große“ Nachbarschaft hat.

Definitionen

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

${\displaystyle h(X)\geq \varepsilon }$

erfüllt.

Man spricht v​on einer Familie v​on Expander-Graphen, w​enn

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

und w​enn weiterhin

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

und

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

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

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

erfüllt.

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

Beispiele

• Die Cayley-Graphen von ${\displaystyle SL(2,\mathbb {Z} /n\mathbb {Z} )}$ sind Expander, denn für sie gilt ${\displaystyle \lambda _{1}>{\frac {3}{16}}}$. Nach der noch unbewiesenen Selberg-Vermutung sollte sogar stets ${\displaystyle \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 ${\displaystyle PGL(2,\mathbb {Q} _{p})/PGL(2,\mathbb {Z} _{p})}$ unter gewissen Gruppenwirkungen.[1]

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

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

Einzelnachweise

1. Lubotzky, Phillips, Sarnak: Ramanujan graphs. Combinatorica 8 (1988), no. 3, 261–277.
2. Kolmogorow, Bārzdiņš: On the realization of networks in three-dimensional space. (1967), in: Selected Works of Kolmogorov, Volume 3, Kluwer Academic Publishers, Dordrecht, 1993.