Ostatnio uczyłem ekspanderów i wprowadziłem pojęcie grafów ramanujańskich. Michael Forbes zapytał, dlaczego tak się nazywają, i musiałem przyznać, że nie wiem. Ktoś?
źródło
Ostatnio uczyłem ekspanderów i wprowadziłem pojęcie grafów ramanujańskich. Michael Forbes zapytał, dlaczego tak się nazywają, i musiałem przyznać, że nie wiem. Ktoś?
Aby dodać trochę treści do odpowiedzi tutaj, wyjaśnię pokrótce przypuszczenie Ramanujana.
Po pierwsze, przypuszczenie Ramanujana jest w rzeczywistości twierdzeniem udowodnionym przez Eichlera i Igusę. Oto jeden ze sposobów, aby to stwierdzić. Niech oznacza liczbę całkowych rozwiązań równania kwadratowego . Jeśli , to m r m ( n ) = c m Σ d | n d + O ( n 1 / 2 + ε ) ε > 0 c m m
Lubtozky, Phillips i Sarnak skonstruowali swoje ekspandery na podstawie tego wyniku. Nie znam szczegółów ich analizy, ale myślę, że podstawową ideą jest skonstruowanie wykresu Cayleya dla pierwszej that , przy użyciu generatorów określonych przez każdą sumę - rozkład czterech kwadratów p , gdzie p jest kwadratowym modułem reszty modulo q . Następnie odnoszą wartości własne tego wykresu Cayleya do r_ {2q} (p ^ k) dla liczb całkowitych k . q 1 mod 4p q r 2 q ( p k ) k
Odwołaniem, innym niż sam papier Lubotzky'ego-Phillipsa-Sarnaka, jest krótki opis Nogi Alona w Narzędziach z Wyższej Algebry .
Wikipedia udziela tej odpowiedzi dość szybko. Cytowanie
Artykuł, o którym mowa, to wykresy Ramanujana A. Lubotzky, R. Phillips i P. Sarnak, COMBINATORICA Tom 8, Numer 3 (1988), 261-277, DOI: 10.1007 / BF02126799.
źródło