www.wikidata.de-de.nina.az

Expander Graph In der Mathematik sind en Familien von Graphen die gleichzeitig dünn und hochzusammenhängend sind und seh

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 Bearbeiten

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 Bearbeiten

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

Literatur Bearbeiten

  • 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 Bearbeiten

Einzelnachweise Bearbeiten

  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.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
In der Mathematik sind Expander Graphen Familien von Graphen die gleichzeitig dunn und hochzusammenhangend sind und sehr gute Stabilitatseigenschaften haben sich also nicht durch Entfernen relativ weniger Kanten in mehrere Zusammenhangskomponenten zerlegen lassen Anschaulich heisst das dass jede kleine Teilmenge von Knoten eine relativ grosse Nachbarschaft hat Inhaltsverzeichnis 1 Definitionen 2 Beispiele 3 Literatur 4 Weblinks 5 EinzelnachweiseDefinitionen BearbeitenEin Graph X E K displaystyle X E K nbsp ist ein e displaystyle varepsilon nbsp Expander wenn seine Cheeger Konstante die Ungleichung h X e displaystyle h X geq varepsilon nbsp erfullt Man spricht von einer Familie von Expander Graphen wenn es ein e gt 0 displaystyle varepsilon gt 0 nbsp gibt so dass alle Graphen der Familie e displaystyle varepsilon nbsp Expander sind und wenn weiterhin die Knotenzahl der Graphen gegen Unendlich geht fur jedes N N displaystyle N in mathbb N nbsp gibt es in der Familie nur endlich viele Graphen der Familie mit weniger als N displaystyle N nbsp Knoten und es eine gleichmassige obere Schranke v displaystyle v nbsp fur den Knotengrad der Graphen gibt Wegen der Cheeger Buser Ungleichung ist die erste Bedingung aquivalent zu der Forderung dass es ein e gt 0 displaystyle varepsilon prime gt 0 nbsp gibt so dass fur alle Graphen der Familie der zweitkleinste Eigenwert l 1 displaystyle lambda 1 nbsp der Laplace Matrix die Ungleichung l 1 X e displaystyle lambda 1 X geq varepsilon prime nbsp erfullt Der Name Expander Graph erklart sich durch die folgende Eigenschaft von e displaystyle varepsilon nbsp Expandern mit oberer Schranke v displaystyle v nbsp fur den Knotengrad fur einen Knoten x displaystyle x nbsp ist die Anzahl der Knoten vom Abstand n displaystyle leq n nbsp mindestens min E 2 1 e v n displaystyle min left frac mid E mid 2 left 1 frac varepsilon v right n right nbsp Beispiele BearbeitenDie Cayley Graphen von S L 2 Z n Z displaystyle SL 2 mathbb Z n mathbb Z nbsp sind Expander denn fur sie gilt l 1 gt 3 16 displaystyle lambda 1 gt frac 3 16 nbsp Nach der noch unbewiesenen Selberg Vermutung sollte sogar stets l 1 1 4 displaystyle lambda 1 geq frac 1 4 nbsp 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 Raume P G L 2 Q p P G L 2 Z p displaystyle PGL 2 mathbb Q p PGL 2 mathbb Z p nbsp unter gewissen Gruppenwirkungen 1 Es gibt verschiedene Argumente dass bestimmte Klassen von Zufallsgraphen mit positiver Wahrscheinlichkeit oder sogar mit Wahrscheinlichkeit 1 displaystyle 1 nbsp Expander Graphen oder sogar Ramanujan Graphen sind Historisch wurde die erste solche Klasse 1967 von Kolmogorov Barzdins beschrieben 2 Literatur BearbeitenAlexander Lubotzky Discrete groups expanding graphs and invariant measures With an appendix by Jonathan D Rogawski Progress in Mathematics 125 Birkhauser 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 OnlineWeblinks BearbeitenE Kowalski Expander Graphs N Linial A Wigderson Expander Graphs and their applicationsEinzelnachweise Bearbeiten Lubotzky Phillips Sarnak Ramanujan graphs Combinatorica 8 1988 no 3 261 277 Kolmogorow Barzdins On the realization of networks in three dimensional space 1967 in Selected Works of Kolmogorov Volume 3 Kluwer Academic Publishers Dordrecht 1993 Abgerufen von https de wikipedia org w index php title Expander Graph amp oldid 218765585