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.[1]

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.[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

Lubotzky, Phillips, Sarnak: Ramanujan graphs. Combinatorica 8 (1988), no. 3, 261–277.
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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.

[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.