Wykres Ramanujana - Ramanujan graph

W widmowej teorii grafów , A Ramanujan wykres , to graf regularny którego widmowa luka jest prawie tak duży, jak to możliwe (patrz ekstremalną teorii grafów ). Takie wykresy są doskonałymi ekspanderami widmowymi . Jak zauważa w artykule przeglądowym Murty'ego, wykresy Ramanujan „łączą różne gałęzie czystej matematyki, a mianowicie teorię liczb , teorię reprezentacji i geometrię algebraiczną ”. Te wykresy są pośrednio nazwane imieniem Srinivasy Ramanujan ; ich nazwa pochodzi od przypuszczenia Ramanujana-Peterssona , która została użyta przy konstrukcji niektórych z tych wykresów.

Definicja

Pozwolić być połączone -regular wykres z wierzchołków i pozwolić być wartości własne tej macierzy przylegania do (lub widma w ). Ponieważ jest połączony i regularny, jego wartości własne spełniają . ${\ Displaystyle G}$${\displaystyle d}$${\ Displaystyle n}$${\ Displaystyle \ lambda _ {1} \ geq \ lambda _ {2} \ geq \ cdots \ geq \ lambda _ {n}}$${\ Displaystyle G}$${\ Displaystyle G}$${\ Displaystyle G}$${\displaystyle d}$${\displaystyle d=\lambda_{1}>\lambda_{2}}$ ${\ Displaystyle \ geq \ cdots \ geq \ lambda _ {n} \ geq -d}$

Zdefiniuj . Połączony graf regularny to graf Ramanujan, jeśli . ${\ Displaystyle \ lambda (G) = \ max _ {i \ neq 1} | \ lambda _ {i} | = \ max (| \ lambda _ {2} | | \ lambda _ {n} |)}$${\displaystyle d}$${\ Displaystyle G}$${\ Displaystyle \ lambda (G) \ leq 2 {\ sqrt {d-1}}}$

Wiele źródeł używa alternatywnej definicji (jeśli istnieje z ), aby zdefiniować wykresy Ramanujan. Innymi słowy, dopuszczamy dodatkowo „małe” wartości własne. Ponieważ wtedy i tylko wtedy, gdy graf jest dwudzielny , będziemy odnosić się do grafów, które spełniają tę alternatywną definicję, ale nie do dwudzielnych grafów Ramanujan z pierwszej definicji . ${\ Displaystyle \ lambda '(G) = \ max _ {| \ lambda _ {i} | <d} | \ lambda _ {i} |}$${\ Displaystyle \ lambda _ {i}}$${\displaystyle |\lambda_{i}|<d}$${\displaystyle -d}$${\ Displaystyle \ lambda _ {n} = -d}$

Jak zauważył Toshikazu Sunada , regularny graf to Ramanujan wtedy i tylko wtedy, gdy jego funkcja Ihara zeta spełnia analogię hipotezy Riemanna .

Przykłady i konstrukcje

Zakończeniu wykres ma widma , a tym samym i na wykresie jest Ramanujana wykres dla każdego . Zakończeniu dwustronnego wykres ma widma , a tym samym jest dwudzielna Ramanujana wykres dla każdego . ${\ Displaystyle K_ {d+1}}$${\displaystyle d,-1,-1,\kropki,-1}$${\ Displaystyle \ lambda (K_ {d + 1}) = 1}$${\displaystyle d>1}$ ${\displaystyle K_{d,d}}$${\displaystyle d,0,0,\kropki,0,-d}$${\displaystyle d}$

Wykres Petersen ma widmo , to jest 3-regularny Ramanujana wykresu. Dwudziestościan wykres jest 5-regular Ramanujan wykres. ${\ Displaystyle 3,1,1,1,1,1,1,-2,-2,-2,-2}$

Paley wykres porządku jest -regular przy wszystkich innych wartości własnych jest , co Paley wykresy nieskończoną rodziny Ramanujana wykresów. ${\displaystyle q}$${\displaystyle {\frac {q-1}{2}}}$${\displaystyle {\frac {-1\pm {\sqrt {q}}}{2}}}$

Matematycy są często zainteresowani konstruowaniem -regularnych wykresów Ramanujan dla każdego ustalonego . Obecne konstrukcje nieskończonych rodzin takich grafów Ramanujan są często algebraiczne. ${\displaystyle d}$${\displaystyle d}$

• Lubotzky , Phillips i Sarnak pokazują, jak skonstruować nieskończoną rodzinę regularnych grafów Ramanujan, gdy jest liczbą pierwszą i . Ich dowód wykorzystuje przypuszczenie Ramanujan , które doprowadziło do nazwy grafów Ramanujana. Oprócz tego, że są grafami Ramanujan, ich konstrukcja spełnia pewne inne właściwości, na przykład ich obwód jest tam, gdzie jest liczba węzłów.${\ Displaystyle (p + 1)}$${\displaystyle p}$${\ Displaystyle p \ równoważ 1 {\ pmod {4}}}$${\ Displaystyle \ Omega (\ log _ {p} (n))}$${\ Displaystyle n}$
• Morgenstern przedłużył budowę Lubotzky, Phillips i Sarnak. Jego rozbudowana konstrukcja sprawdza się zawsze, gdy jest główną siłą .${\displaystyle p}$
• Arnold Pizer udowodnił, że grafy izogenii superosobliwej to Ramanujan, chociaż mają one zwykle mniejszy obwód niż grafy Lubotzky'ego, Phillipsa i Sarnaka. Podobnie jak w przypadku wykresów Lubotzky'ego, Phillipsa i Sarnaka, stopnie tych wykresów są zawsze liczbą pierwszą plus jeden. Wykresy te zostały zaproponowane jako podstawa do post-kwantowej eliptyczny-kryptografii krzywych .
• Adam Marcus , Daniel Spielman i Nikhil Srivastava udowodnili istnienie nieskończenie wielu regularnych dwudzielnych grafów Ramanujan dla dowolnego . Później udowodnili, że istnieją dwudzielne grafy Ramanujan każdego stopnia i każdej liczby wierzchołków. Michael B. Cohen pokazał, jak skonstruować te wykresy w czasie wielomianowym.${\displaystyle d}$${\displaystyle d\geq 3}$

Nadal otwartym problemem jest to, czy istnieje nieskończenie wiele -regularnych (nie dwudzielnych) grafów Ramanujan dla dowolnego . W szczególności problem jest otwarty dla , dla którego najmniejszy przypadek nie jest potęgą pierwotną, a zatem nie jest objęty konstrukcją Morgensterna. ${\displaystyle d}$${\displaystyle d\geq 3}$${\displaystyle d=7}$${\displaystyle d-1}$

Grafy Ramanujana jako grafy ekspandera

Stała w definicji grafów Ramanujana jest najlepszą możliwą stałą dla każdego i dla dużych grafów: innymi słowy, dla każdego i istnieje taka, że ​​wszystkie -regularne grafy z przynajmniej wierzchołkami spełniają . (Patrz poniżej na bardziej precyzyjnych stwierdzeń i próbnych szkiców.) Z drugiej strony, Friedman pokazał, że dla każdego i oraz wystarczająco duża , bezładny -regular wykres -Vertex spełnia z dużym prawdopodobieństwem. Oznacza to, że grafy Ramanujana są w zasadzie najlepszymi możliwymi grafami ekspandera . ${\displaystyle 2{\sqrt {d-1}}}$${\displaystyle d}$${\displaystyle d}$${\ Displaystyle \ epsilon > 0}$${\ Displaystyle n}$${\displaystyle d}$${\ Displaystyle G}$${\ Displaystyle n}$${\ Displaystyle \ lambda (G)> 2 {\ sqrt {d-1}} - \ epsilon}$${\displaystyle d}$${\ Displaystyle \ epsilon > 0}$${\ Displaystyle n}$${\displaystyle d}$${\ Displaystyle n}$${\ Displaystyle G}$${\ Displaystyle \ lambda (G) <2 {\ sqrt {d-1}} + \ epsilon}$

Ze względu na osiągnięcie ciasne związanie na The ekspander mieszanie lematu daje doskonałe granic na równomierność rozkładu krawędzi w Ramanujan wykresów, a wszelkie przypadkowe spacery na wykresach ma logarytmiczną czas mieszania (pod względem liczby wierzchołków): innymi słowy, błądzenie losowe bardzo szybko zbliża się do (równomiernego) rozkładu stacjonarnego . Dlatego średnice grafów Ramanujan są również ograniczone logarytmicznie pod względem liczby wierzchołków. ${\ Displaystyle \ lambda (G)}$

Ekstremalność grafów Ramanujan

Jeśli jest -grafem regularnym o średnicy , twierdzenie wynikające z Nogi Alona stwierdza ${\ Displaystyle G}$${\displaystyle d}$ ${\ Displaystyle m}$

${\ Displaystyle \ lambda _ {2} (G) \ geq 2 {\ sqrt {d-1}} - {\ frac {2 {\ sqrt {d-1}} -1} {\ l piętro m/2 \ r piętro }}.}$

Zawsze, gdy jest -regularny i połączony na co najmniej trzech wierzchołkach, , a zatem . Niech będzie zbiorem wszystkich połączonych grafów regularnych z przynajmniej wierzchołkami. Ponieważ minimalna średnica grafów zbliża się do nieskończoności dla ustalonego i rosnącego , twierdzenie to implikuje wcześniejsze twierdzenie Alona i Boppany, które stwierdza ${\ Displaystyle G}$${\displaystyle d}$${\displaystyle |\lambda_{2}|<d}$${\ Displaystyle \ lambda (G) \ geq \ lambda _ {2}}$${\ Displaystyle {\ mathcal {G}} _ {n} ^ {d}}$${\displaystyle d}$${\ Displaystyle G}$${\ Displaystyle n}$${\ Displaystyle {\ mathcal {G}} _ {n} ^ {d}}$${\displaystyle d}$${\ Displaystyle n}$

${\ Displaystyle \ lim _ {n \ do \ infty} \ inf _ {G \ w {\ mathcal {G}} _ {n} ^ {d}} \ lambda (G) \ geq 2 {\ sqrt {d- 1}}.}$

Nieco silniejsze wiązanie to

${\ Displaystyle \ lambda _ {2} (G) \ geq 2 {\ sqrt {d-1}} \ cdot \ lewo (1-{\ Frac {c} {m ^ {2}}} \ po prawej)}$

gdzie . Zarys dowodu jest następujący. Weź . Niech będzie pełnym -arnym drzewem wysokości (każdy wewnętrzny wierzchołek ma dzieci) i niech będzie jego macierzą sąsiedztwa. Chcemy to udowodnić , gdzie . Zdefiniuj funkcję według , gdzie jest odległością od do korzenia . Można to zweryfikować i to jest rzeczywiście największa wartość własna . Teraz i być parę wierzchołków w odległości w i zdefiniować ${\displaystyle c\ok 2\pi ^{2}}$${\ Displaystyle k = \ lewo \ l piętro {\ Frac {m} {2}} \ prawo \ r piętro -1}$${\displaystyle T_{d,k}}$${\ Displaystyle (d-1)}$${\displaystyle k}$${\displaystyle d-1}$${\displaystyle A_{d,k}}$${\ Displaystyle \ lambda _ {2} (G) \ geq \ lambda _ {1} (T_ {d, k}) = 2 {\ sqrt {d-1}} \ cos \ teta}$${\ Displaystyle \ theta = {\ Frac {\ pi} {k + 2}}}$${\ Displaystyle g: V (T_ {d, k}) \ rightarrow \ mathbb {R}}$${\ Displaystyle g (x) = (d-1) ^ {- \ delta /2} \ cdot \ sin ((k + 1 - \ delta) \ theta)}$${\ Displaystyle \ delta}$${\displaystyle x}$${\displaystyle T_{d,k}}$${\ Displaystyle A_ {t, k} g = \ lambda _ {1} (T_ {d, k}) g}$${\ Displaystyle \ lambda _ {1}(T_ {d, k})}$${\displaystyle A_{d,k}}$${\displaystyle s}$${\displaystyle t}$${\ Displaystyle m}$${\ Displaystyle G}$

${\ Displaystyle f (v) = {\ zacząć {przypadki} c_ {1} g (v_ {s}) i {\ tekst {dla}} v {\ tekst {na odległość}} \ leq k {\ tekst {od }}s,\\-c_{2}g(v_{t})&{\text{dla }}v{\text{ w odległości }}\leq k{\text{ od }}t,\\0& {\text{w przeciwnym razie}}\end{przypadki}}}$

gdzie jest wierzchołkiem, w którym odległość do korzenia jest równa odległości od do i symetrycznej do . (Można to potraktować jako „osadzenie” dwóch rozłącznych kopii , z kilkoma wierzchołkami zwiniętymi w jeden.) Wybierając właściwie wartość dodatnich liczb rzeczywistych otrzymujemy , dla bliskich i dla bliskich . Następnie przez twierdzenie o min-maksach otrzymujemy${\displaystyle v_{s}}$${\displaystyle T_{d,k}}$${\displaystyle v}$${\displaystyle s}$${\displaystyle v_{t}}$${\displaystyle T_{d,k}}$${\displaystyle c_{1},c_{2}}$${\ Displaystyle f\ sprawca 1}$${\ Displaystyle (Af) _ {v} \ geq \ lambda _ {1} (T_ {d, k}) f_ {v}}$${\displaystyle v}$${\displaystyle s}$${\ Displaystyle (Af) _ {v} \ leq \ lambda _ {1} (T_ {d, k}) f_ {v}}$${\displaystyle v}$${\displaystyle t}$

zgodnie z życzeniem.

Zobacz też

• Wykres ekspandera
• Lemat mieszania ekspandera
• Teoria grafów spektralnych

Bibliografia

Dalsza lektura

• Giuliana Davidoff ; Piotra Sarnaka ; Alaina Valette'a (2003). Elementarna teoria liczb, teoria grup i grafy Ramanujan . Teksty studenckie LMS. 55 . Wydawnictwo Uniwersytetu Cambridge . Numer ISBN 0-521-53143-8. OCLC  50253269 .
• T. Sunada (1985). „Funkcje L w geometrii i niektórych zastosowaniach”. Notatki z wykładu z matematyki . Notatki z wykładu z matematyki. 1201 : 266-284. doi : 10.1007/BFb0075662 . Numer ISBN 978-3-540-16770-9.

Linki zewnętrzne

• Artykuł ankietowy autorstwa M. Ram Murty