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 \epsilon$

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 Knoten)

und

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

Wegen der Cheeger-Buser-Ungleichung ist die erste Bedingung äquivalent zu der Forderung, dass es ein $\epsilon ^{\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 für den Knotengrad: für einen Knoten 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 Expander-Graphen oder sogar Ramanujan-Graphen sind. Historisch wurde die erste solche Klasse 1967 von Kolmogorov-Barzdins beschrieben.

Basierend auf einem Artikel in:

Wikipedia.de