Ramanujan-Graph

Im mathematischen Gebiet d​er Graphentheorie s​ind Ramanujan-Graphen Graphen m​it besonderen Regularitäts- u​nd Stabilitätseigenschaften, d​ie deshalb i​n verschiedenen Gebieten d​er Informatik u​nd Mathematik v​on Interesse sind.

Der Graph i​st nach S. Ramanujan benannt, w​obei der Name v​on Alexander Lubotzky, Ralph Phillips u​nd Peter Sarnak stammt, d​ie 1988 Ramanujan-Graphen einführten (sie benutzten e​in Resultat v​on Ramanujan).

Definition

Ein zusammenhängender ${\displaystyle k}$-regulärer Graph ist ein Ramanujan-Graph, wenn alle Eigenwerte ${\displaystyle \lambda }$ der Adjazenzmatrix entweder ${\displaystyle \lambda =\pm k}$ oder ${\displaystyle \mid \lambda \mid \leq 2{\sqrt {k-1}}}$ erfüllen.

Äquivalent lassen sich Ramanujan-Graphen dadurch charakterisieren, dass das Analog der Riemann-Vermutung für die Iharasche Zetafunktion gilt: alle Polstellen im Bereich ${\displaystyle 0\leq Re(s)\leq 1}$ liegen auf der Geraden ${\displaystyle Re(s)={\frac {1}{2}}}$.

Ramanujan-Graphen als optimale Expander

Expander-Graphen sind Graphen mit sehr guten Stabilitätseigenschaften (d. h., sie lassen sich nicht durch Entfernen relativ weniger Kanten in mehrere Zusammenhangskomponenten zerlegen), die deshalb in Mathematik und Informatik von großem Interesse sind. Eine Möglichkeit, die Expansitivität eines ${\displaystyle k}$-regulären Graphen zu messen, ist durch den zweitgrößten Eigenwert ${\displaystyle \lambda _{2}}$ der Adjazenzmatrix. (Der größte Eigenwert ${\displaystyle \lambda _{1}}$ ist für einen ${\displaystyle k}$-regulären Graphen immer ${\displaystyle \lambda _{1}=k}$.)

Man kann beweisen, dass für einen ${\displaystyle k}$-regulären Graphen mit ${\displaystyle n}$ Ecken eine Ungleichung

${\displaystyle \lambda _{2}\geq 2{\sqrt {k-1}}-o(1)}$

gilt. Andererseits gilt für Ramanujan-Graphen ${\displaystyle \lambda _{2}\leq 2{\sqrt {k-1}}}$, diese haben für große ${\displaystyle n}$ also annähernd optimale Expander-Eigenschaft.

Konstruktionen

Es gibt verschiedene Konstruktionen von Ramanujan-Graphen. Für Primzahlen ${\displaystyle p}$ benutzten Lubotzky-Philips-Sarnak[1][2] die Ramanujan-Vermutung um zu beweisen, dass gewisse Quotienten des p-adischen symmetrischen Raums ${\displaystyle PGL(2,\mathbb {Q} _{p})/PGL(2,\mathbb {Z} _{p})}$ ${\displaystyle p}$-reguläre Ramanujan-Graphen sind. Marcus-Spielman-Srivastava[3] konstruieren ${\displaystyle k}$-reguläre Ramanujan-Graphen für beliebige ${\displaystyle k}$.

Beispiele

Der Petersen-Graph i​st ein Ramanujan-Graph.

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

Einzelnachweise

1. Alexander Lubotzky, Ralph Phillips, Peter Sarnak: Ramanujan graphs. Combinatorica 8 (1988), no. 3, 261–277. doi:10.1007/BF02126799.
2. Kapitel 7.3 in Lubotzky, op.cit.
3. Adam Marcus, Daniel Spielman, Nikhil Srivastava: Interlacing families I: Bipartite Ramanujan graphs of all degrees. Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium. online (PDF; 196 kB)