Wykres Ramanujana

W matematycznej dziedzinie teorii grafów , grafy Ramanujana są grafami o szczególnych właściwościach regularności i stabilności, które są z tego powodu interesujące w różnych dziedzinach informatyki i matematyki.

Wykres został nazwany na cześć S. Ramanujana , nazwiska Alexandra Lubotzky'ego , Ralpha Phillipsa i Petera Sarnaka , którzy wprowadzili wykresy Ramanujana w 1988 roku (wykorzystali wynik z Ramanujana).

definicja

Połączony - regularna wykres jest Ramanujana wykres, jeżeli wszystkie wartości własne tej macierzy przylegania spełniają warunek albo czy . ${\ displaystyle k}$ ${\ displaystyle \ lambda}$${\ displaystyle \ lambda = \ pm k}$${\ displaystyle \ mid \ lambda \ mid \ leq 2 {\ sqrt {k-1}}}$

Grafy Ramanujana można w sposób równoważny scharakteryzować przez analogię hipotezy Riemanna dla funkcji zeta Iharasa : wszystkie bieguny w obszarze leżą na linii prostej . ${\ Displaystyle 0 \ równoważnik Re (s) \ równoważnik 1}$ ${\ displaystyle Re (s) = {\ Frac {1} {2}}}$

Grafy Ramanujana jako optymalny ekspander

Grafy ekspandera to wykresy o bardzo dobrych właściwościach stabilności (tj. Nie da się ich rozbić na kilka połączonych ze sobą komponentów poprzez usunięcie stosunkowo niewielu krawędzi), które są zatem bardzo interesujące w matematyce i informatyce. Jedną z możliwości pomiaru ekspansywności wykresu nieregularnego jest druga co do wielkości wartość własna macierzy sąsiedztwa. (Największa wartość własna jest zawsze dla wykresu -regularnego ). ${\ displaystyle k}$${\ displaystyle \ lambda _ {2}}$${\ displaystyle \ lambda _ {1}}$${\ displaystyle k}$${\ displaystyle \ lambda _ {1} = k}$

Można udowodnić, że dla wykresu-nieregularnego z wierzchołkami występuje nierówność${\ displaystyle k}$${\ displaystyle n}$

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

dotyczy. Z drugiej strony dotyczy to grafów Ramanujana , że mają one prawie optymalne właściwości ekspandera dla dużych . ${\ displaystyle \ lambda _ {2} \ leq 2 {\ sqrt {k-1}}}$${\ displaystyle n}$

Konstrukcje

Istnieją różne konstrukcje grafów Ramanujana. Dla liczb pierwszych Lubotzky-Philips-Sarnak użył hipotezy Ramanujana, aby udowodnić, że pewne ilorazy p- adycznej przestrzeni symetrycznej są -regularnymi wykresami Ramanujana. Marcus-Spielman-Srivastava konstruuje -regularne wykresy Ramanujana dla arbitralności . ${\ displaystyle p}$ ${\ Displaystyle PGL (2 \ mathbb {Q} _ {p}) / PGL (2 \ mathbb {Z} _ {p})}$ ${\ displaystyle p}$${\ displaystyle k}$${\ displaystyle k}$

Przykłady

Wykres Petersen jest Ramanujana wykresu.

literatura

• Alexander Lubotzky : Grupy dyskretne, wykresy rozszerzające i miary niezmienne. Z dodatkiem Jonathana D. Rogawskiego. Progress in Mathematics, 125. Birkhäuser Verlag, Bazylea, 1994. ISBN 3-7643-5075-X

Indywidualne dowody

1. ↑ Alexander Lubotzky, Ralph Phillips, Peter Sarnak: Wykresy Ramanujana . Combinatorica 8 (1988) nr 3, 261-277. doi : 10.1007 / BF02126799 .
2. ↑ Rozdział 7.3 w Lubotzky, op. Cit.
3. ↑ Adam Marcus , Daniel Spielman , Nikhil Srivastava : Przeplatające się rodziny I: Dwuczęściowe wykresy Ramanujana wszystkich stopni . Podstawy informatyki (FOCS), 54. doroczne sympozjum IEEE 2013. online (pdf)