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 ist ein -Expander, wenn seine Cheeger-Konstante die Ungleichung

erfüllt.

Man spricht von einer Familie von Expander-Graphen, wenn

  • es ein gibt, so dass alle Graphen der Familie -Expander sind,

und wenn weiterhin

  • die Knotenzahl der Graphen gegen Unendlich geht (für jedes 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 gibt, so dass für alle Graphen der Familie der zweitkleinste Eigenwert der Laplace-Matrix die Ungleichung

erfüllt.

Der Name „Expander-Graph“ erklärt sich durch die folgende Eigenschaft von -Expandern mit oberer Schranke für den Knotengrad: für einen Knoten ist die Anzahl der Knoten vom Abstand mindestens .

Beispiele

  • Die Cayley-Graphen von sind Expander, denn für sie gilt . Nach der noch unbewiesenen Selberg-Vermutung sollte sogar stets sein.
  • Lubotzky-Philips-Sarnak konstruieren Familien von Ramanujan-Graphen als Quotienten p-adischer symmetrischer Räume unter gewissen Gruppenwirkungen.[1]
  • 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.[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

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.