Srinavasa Ramanujan
|
Ramanujan-Graphen "vereinen mehrere Zweige der reinen Mathematik, nämlich Zahlentheorie, Darstellungtheorie und algebraische Geometrie". Sie sind nach Srinivasa Ramanujan benannt und stammen von der Ramanujan-Petersson-Vermutung, die bei der Konstruktion einiger dieser Graphen verwendet wurde |
ta ஸ்ரீனிவாஸ ராமானுஜன் |
Im mathematischen Gebiet der Graphentheorie sind Ramanujan-Graphen Graphen mit besonderen Regularitäts- und Stabilitätseigenschaften, die deshalb in verschiedenen Gebieten der Informatik und Mathematik von Interesse sind.
Der Graph ist nach S. Ramanujan benannt, wobei der Name von Alexander Lubotzky, Ralph Phillips und Peter Sarnak stammt, die 1988 Ramanujan-Graphen einführten (sie benutzten ein Resultat von Ramanujan).
Definition[edit | edit source]
Ein zusammenhängender k-regulärer Graph ist ein Ramanujan-Graph, wenn alle Eigenwerte λ der Adjazenzmatrix entweder λ= k o |λ|≤2 ✓(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 0≤Re(s)≤1 liegen auf der Geraden Re(s)≤½.
Ramanujan-Graphen als optimale Expander[edit | edit source]
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 k-regulären Graphen zu messen, ist durch den zweitgrößten Eigenwert λ2 der Adjazenzmatrix. (Der größte Eigenwert λ1 ist für einen k-regulären Graphen immer λ1=k.)
Man kann beweisen, dass für einen <math>k</math>-regulären Graphen mit <math>n</math> Ecken eine Ungleichung
- λ2≥ ✓{k-1}-o(1)
gilt. Andererseits gilt für Ramanujan-Graphen λ2≤ ✓{k-1}, diese haben für große <math>n</math> also annähernd optimale Expander-Eigenschaft.
Konstruktionen[edit | edit source]
Es gibt verschiedene Konstruktionen von Ramanujan-Graphen. Für Primzahlen p benutzten Lubotzky-Philips-Sarnak[1][2] die Ramanujan-Vermutung um zu beweisen, dass gewisse Quotienten des p-adischen symmetrischen Raums PGL(2,Q_p/PGL(2,Z_p) p-reguläre Ramanujan-Graphen sind. Marcus-Spielman-Srivastava[3] konstruieren <math>k</math>-reguläre Ramanujan-Graphen für beliebige k.
Beispiele[edit | edit source]
Der Petersen-Graph ist ein Ramanujan-Graph.
Literatur[edit | edit source]
- 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
- Ram Murty M. 2003 Ramunajan Graphs J Ramunajan Math soc.
Einzelnachweise[edit | edit source]
- ↑ Alexander Lubotzky, Ralph Phillips, Peter Sarnak: Ramanujan graphs. Combinatorica 8 (1988), no. 3, 261–277. download.
- ↑ Kapitel 7.3 in Lubotzky, op.cit.
- ↑ 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)