Topologie von Flächen CIII

“In the last two decades, the theory of Ramanujan graphs has gained prominence primarily for two reasons. First, from a practical viewpoint, these graphs resolve an extremal problem in communication network theory. Second, from a more aesthetic viewpoint, they fuse diverse branches of pure mathematics, namely, number theory, representation theory and algebraic geometry.” (M.R.Murty)

Vor 2 Wochen hatten wir über Expander-Graphen geschrieben, “stabile Telefon-Netze”, d.h. Graphen, die sich nicht durch Entfernen weniger Kanten in (annähernd gleich große) Komponenten zerlegen lassen.

Letzte Woche hatten wir geschrieben, daß der (zweite) Eigenwert λ des Laplace-Operators ein gutes Maß für die Expansion eines Graphen ist.

Insbesondere hatten wir Selbergs Konstruktion erwähnt, der mittels hyperbolischer Geometrie Expander-Graphen mit λ≥ 3/16 konstruiert.

Heute soll es um eine bessere (sogar die bestmögliche) Methode zur Konstruktion von Expander-Graphen gehen, nämlich die Konstruktion von sogenannten Ramanujan-Graphen.

Ramanujan-Graphen sind, per Definition d-reguläre Graphen (d.h. von jeder Ecke geht die gleiche Zahl d von Kanten aus), für deren zweiten Eigenwert die Ungleichung
λ≥ d – 2(d-1)^1/2
gilt.
(off topic: kennt eigentlich irgendjemand das HTML-Symbol für die Quadratwurzel ???)

Zum Beispiel der Petersen-Graph ist ein Ramanujan-Graph mit d=3 und λ=0,172… :

Warum gerade Ramanujan-Graphen?

Wenn man irgendeine Folge X_n von d-regulären Graphen hat, deren Ecken-Anzahl n gegen unendlich geht, dann ist der Grenzwert von λ(X_n) höchstens d – 2(d-1)^1/2.

Folgen von Ramanujan-Graphen sind also die bestmöglichen Expander-Folgen, es kann keine besseren geben.

(Interessanterweise sind in einem statistischen Sinn fast alle Graphen Ramanujan-Graphen. Trotzdem brauchen Konstruktionen expliziter Beispiele anspruchsvolle Mathematik.)

Woher kommt der Name Ramanujan-Graph?

Ramanujan war ein indischer Zahlentheoretiker, der unter anderem viele zahlentheoretische Erkenntnisse aus der Untersuchung von Modulfunktionen gewonnen hat. (Dazu nächste Woche.)
Die sogenannte Ramanujan-Vermutung aus der Theorie der Modulformen ist eine Ungleichung für die Koeffizienten einer bestimmten Modulform, nämlich der Dedekind’schen η-Funktion (siehe TvF 100): es geht um die Koeffizienten τ(n) der Reihenentwicklung
qΠ_m(1-q^m)²⁴=Σ_nτ(n)qⁿ
Die Ramanujan-Vermutung besagt, daß für Primzahlen p die Ungleichung
Iτ(p)I≤2p^11/2
gelten muß.

Die Ramanujan-Vermutung wurde 1974 von Deligne bewiesen, als Konsequenz der Weil-Vermutung. Es erschließt sich sicher nicht auf den ersten Blick (und vermutlich auch nicht auf den zweiten oder dritten – ich habe nicht versucht, den Beweis zu lesen), was diese Ungleichung mit der Konstruktion von Expander-Graphen zu tun hat.

Konstruktion von Lubotzky-Philipps-Sarnak

Die Arbeit von Lubotzky-Philipps-Sarnak verwendet die p-adischen Zahlen Q_p, Z_p und den “p-adischen symmetrischen Raum” PGL₂(Q_p)/PGL₂(Z_p). Dieser “p-adische symmetrische Raum” ist aber eigentlich kein symmetrischer Raum, sondern ein Baum, also ein Graph ohne Kreise.
Die Ramanujan-Graphen erhält man als “Quotienten” dieses p-adischen symmetrischen Raums, in Analogie zur Bildung hyperbolischer Flächen:

Im Fall der hyperbolischen Ebene (TvF 64) konnte man ja durch “Herausteilen” passender Gruppen hyperbolische Flächen als Quotienten bekommen. (Oder ein einfacheres Beispiel: den flachen Torus bekommt man als Quotient der Ebene, man teilt die Gruppe Z2 heraus, siehe TvF 63)

====>

Quelle: Mathworld

Ähnlich geht es hier im Fall der p-adischen symmetrischen Räume: durch “Herausteilen” passender Gruppen erhält man (p+1)-reguläre Graphen als Quotienten:

===>

Lubotzky-Philipps-Sarnak beweisen, daß man mit dieser Konstruktion, für bestimmte Gruppen, auf der rechten Seite Ramanujan-Graphen bekommt.
Der Beweis benutzt neben Modulfunktionen auch tiefliegende Sätze aus der Darstellungstheorie. (Sie beweisen, daß man genau dann einen Ramanujan-Graphen bekommt, wenn es für die Gruppe keine sogenannten nichttrivialen Komplementärreihendarstellungen gibt.) Jedenfalls wird im Beweis auch irgendwo die Ramanujan-Vermutung für Modulformen verwendet, daher wohl der Name “Ramanujan-Graph”.

Teil 1, Teil 2, Teil 3, Teil 4, Teil 5, Teil 6, Teil 7 , Teil 8, Teil 9 , Teil 10 ,Teil 11, Teil 12, Teil 13, Teil 14, Teil 15, Teil 16, Teil 17, Teil 18, Teil 19, Teil 20, Teil 21, Teil 22, Teil 23, Teil 24, Teil 25, Teil 26, Teil 27, Teil 28, Teil 29, Teil 30, Teil 31, Teil 32, Teil 33, Teil 34, Teil 35, Teil 36, Teil 37, Teil 38, Teil 39, Teil 40, Teil 41, Teil 42, Teil 43, Teil 44, Teil 45, Teil 46, Teil 47, Teil 48, Teil 49, Teil 50, Teil 51, Teil 52, Teil 53, Teil 54, Teil 55, Teil 56, Teil 57, Teil 58, Teil 59, Teil 60, Teil 61, Teil 62, Teil 63, Teil 64, Teil 65, Teil 66, Teil 67, Teil 68, Teil 69, Teil 70, Teil 71, Teil 72, Teil 73, Teil 74, Teil 75, Teil 76, Teil 77, Teil 78, Teil 79, Teil 80, Teil 81, Teil 82, Teil 83, Teil 84, Teil 85, Teil 86, Teil 87, Teil 88, Teil 89, Teil 90, Teil 91, Teil 92, Teil 93, Teil 94, Teil 95, Teil 96, Teil 97, Teil 98, Teil 99, Teil 100, Teil 101, Teil 102