Граф Рамануджана

У спектральній теорії графів граф Рамануджана, названий на честь індійського математика Рамануджана, — це регулярний граф, спектральна щілина^[en] якого майже настільки велика, наскільки це можливо (див. статтю «Екстремальна теорія графів»). Такі графи є чудовими спектральними експандерами.

Прикладами графів Рамануджана є кліки, повні двочасткові графи ${\displaystyle K_{n,n}}$ та граф Петерсена. Як зауважує Мурті^[1], графи Рамануджана «сплавляють воєдино різні гілки чистої математики, а саме, теорію чисел, теорію представлень та алгебричну геометрію». Як зауважив Тосікадзу Сунада, регулярний граф є графом Рамануджана тоді й лише тоді, коли його дзета-функція Іхари^[en] задовольняє аналогу гіпотези Рімана^[2].

Визначення

Нехай ${\displaystyle G}$ — зв'язний ${\displaystyle d}$-регулярний графом із ${\displaystyle n}$ вершинами, а ${\displaystyle \lambda _{0}\geqslant \lambda _{1}\geqslant \cdots \geqslant \lambda _{n-1}}$ — власні числа матриці суміжності графа ${\displaystyle G}$. Оскільки граф ${\displaystyle G}$ зв'язний і ${\displaystyle d}$-регулярний, його власні числа задовольняють нерівності ${\displaystyle d=\lambda _{0}>\lambda _{1}\geqslant \cdots \geqslant \lambda _{n-1}\geqslant -d}$. Якщо існує значення ${\displaystyle \lambda _{i}}$, для котрого ${\displaystyle |\lambda _{i}|<d}$, визначимо

${\displaystyle \lambda (G)=\max _{|\lambda _{i}|<d}|\lambda _{i}|.\,}$

${\displaystyle d}$-Регулярний граф ${\displaystyle G}$ є графом Рамануджана, якщо ${\displaystyle \lambda (G)\leqslant 2{\sqrt {d-1}}}$.

Граф Рамануджана описується як регулярний граф, дзета-функція Іхари^[en] якого задовольняє аналогу гіпотези Рімана.

Екстремальність графів Рамануджана

Для фіксованого значення ${\displaystyle d}$ і великого ${\displaystyle n}$ ${\displaystyle d}$-регулярні графи Рамануджана з ${\displaystyle n}$ вершинами майже мінімізують ${\displaystyle \lambda (G)}$. Якщо ${\displaystyle G}$ є ${\displaystyle d}$-регулярним графом із діаметром ${\displaystyle m}$, теорема Алона^[3] стверджує

${\displaystyle \lambda _{1}\geqslant 2{\sqrt {d-1}}-{\frac {2{\sqrt {d-1}}-1}{\lfloor m/2\rfloor }}.}$

Якщо ${\displaystyle G}$ є ${\displaystyle d}$-регулярним і зв'язним принаймні на трьох вершинах, ${\displaystyle |\lambda _{1}|<d}$, а тому ${\displaystyle \lambda (G)\geqslant \lambda _{1}}$. Нехай ${\displaystyle {\mathcal {G}}_{n}^{d}}$ — множина всіх зв'язних ${\displaystyle d}$-регулярних графів ${\displaystyle G}$ принаймні з ${\displaystyle n}$ вершинами. Оскільки мінімальний діаметр графа в ${\displaystyle {\mathcal {G}}_{n}^{d}}$ прямує до нескінченності за фіксованого ${\displaystyle d}$ і збільшення ${\displaystyle n}$, з цієї теореми випливає теорема Алона й Боппана, яка стверджує

${\displaystyle \lim _{n\to \infty }\inf _{G\in {\mathcal {G}}_{n}^{d}}\lambda (G)\geqslant 2{\sqrt {d-1}}.}$

Трохи строгіша межа

${\displaystyle \lambda _{1}\geqslant 2{\sqrt {d-1}}\cdot \left(1-{\frac {c}{m^{2}}}\right),}$

де ${\displaystyle c\approx 2\pi ^{2}}$. Суть доведення Фрідмана така. Візьмемо ${\displaystyle k=\left\lfloor {\frac {m}{2}}\right\rfloor -1}$. Нехай ${\displaystyle T_{d,k}}$ — ${\displaystyle d}$-регулярне дерево висоти ${\displaystyle k}$, і ${\displaystyle A_{T_{k}}}$ — його матриця суміжності. Ми хочемо довести, що ${\displaystyle \lambda (G)\geqslant \lambda (T_{d,k})=2{\sqrt {d-1}}\cos \theta }$ для деякого ${\displaystyle \theta }$, що залежить тільки від ${\displaystyle m}$. Визначимо функцію ${\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 \theta }$ близьким до ${\displaystyle 2\pi /m}$, можна довести, що ${\displaystyle A_{t,k}g=\lambda (T_{d,k})g}$. Тепер нехай ${\displaystyle s}$ і ${\displaystyle t}$ — пара вершин на відстані ${\displaystyle m}$ і визначимо

${\displaystyle f(v)={\begin{cases}c_{1}g(v_{s})&&dist(v,s)\leqslant k,\\-c_{2}g(v_{t})&&dist(v,t)\leqslant k,\\0&\end{cases}}}$

де ${\displaystyle v_{s}}$ — вершина в ${\displaystyle T_{d,k}}$, відстань від якої до кореня дорівнює відстані від ${\displaystyle v}$ до ${\displaystyle s}$ (${\displaystyle dist(v,s)}$) і симетрична для ${\displaystyle v_{t}}$. Вибравши відповідні ${\displaystyle c_{1},c_{2}}$ ми отримаємо ${\displaystyle f\perp 1}$, ${\displaystyle (Af)_{v}\geqslant \lambda (T_{d,k})f_{v}}$ для ${\displaystyle v}$ близьких до ${\displaystyle s}$ і ${\displaystyle (Af)_{v}\leqslant \lambda (T_{d,k})f_{v}}$ для ${\displaystyle v}$ близьких до ${\displaystyle t}$. Тоді, за теоремою про мінімакс, ${\displaystyle \lambda (G)\geqslant fAf^{T}/\|f\|^{2}\geqslant \lambda (T_{d,k})}$.

Побудови

Побудови графів Рамануджана часто алгебричні.

• Лубоцькі, Філіпс та Сарнак^[4] показали, як побудувати нескінченне сімейство ${\displaystyle (p+1)}$-регулярних графів Рамануджана, коли ${\displaystyle p}$ є простим числом і ${\displaystyle p\equiv 1{\pmod {4}}}$. Їхнє доведення використовує гіпотезу Рамануджана, звідки й отримали назву графи Рамануджана. Крім властивості бути графами Рамануджана, їхня побудова має низку інших властивостей. Наприклад, обхват дорівнює ${\displaystyle \Omega (\log _{p}(n))}$, де ${\displaystyle n}$ — число вузлів.
• Моргенштерн^[5] розширив побудову Лубоцькі, Філліпса та Сарнака. Його побудова допустима, якщо ${\displaystyle p}$ є степенем простого числа.
• Арнольд Піцер довів, що суперсингулярні ізогенії графа^[en] є графами Рамануджана, хоча, як правило, вони мають менший обхват, ніж графи Лубоцькі, Філліпса та Сарнака^[6]. Подібно до графів Лубоцькі, Філіпса та Сарнака, степеня цих графів завжди дорівнюють простому числу + 1. Ці графи пропонуються як базис постквантової еліптичної криптографії^[7].
• Адам Маркус, Даніель Спільман^[8] та Нікхіл Срівастава^[9] довели існування ${\displaystyle d}$-регулярних двочасткових графів Рамануджана для будь-якого ${\displaystyle d}$. Пізніше^[10] вони довели, що існують двочасткові графи Рамануджана будь-якого степеня та з будь-яким числом вершин. Міхаель Б. Коен^[11] показав, як будувати ці графи за поліноміальний час.

Примітки

1. M. Ram Murty. Ramanujan Graphs // J. Ramanujan Math. Soc.. — 2003. — Vol. 18, no. 1. — P. 1-20.
2. Terras, 2011.
3. Nilli, 1991, с. 207–210.
4. Lubotzky, Phillips, Sarnak, 1988, с. 261–277.
5. Morgenstern, 1994, с. 44–62.
6. Pizer, 1990, с. 127–137.
7. Eisenträger, Hallgren, Lauter, Morrison, Petit, 2018, с. 329–368.
8. Німецьке прізвище і німецькою воно має звучати як Шпільман
9. Marcus, Spielman, Srivastava, 2013.
10. Marcus, Spielman, Srivastava, 2015.
11. Cohen, 2016.

Література

• Audrey Terras. Zeta functions of graphs: A stroll through the garden. — Cambridge University Press, 2011. — Т. 128. — (Cambridge Studies in Advanced Mathematics) — ISBN 978-0-521-11367-0.
• Nilli A. On the second eigenvalue of a graph // Discrete Mathematics. — 1991. — Т. 91, вип. 2 (10 листопада). — С. 207–210. — DOI:10.1016/0012-365X(91)90112-F.
• Alexander Lubotzky, Ralph Phillips, Peter Sarnak. Ramanujan graphs // Combinatorica. — 1988. — Т. 8, вип. 3 (10 листопада). — DOI:10.1007/BF02126799.
• Moshe Morgenstern. Existence and Explicit Constructions of q+1 Regular Ramanujan Graphs for Every Prime Power q // Journal of Combinatorial Theory, Series B. — 1994. — Т. 62 (10 листопада). — DOI:10.1006/jctb.1994.1054.
• Arnold K. Pizer. Ramanujan graphs and Hecke operators // Bulletin of the American Mathematical Society. — 1990. — Т. 23, вип. 1 (10 листопада). — С. 127–137. — (New Series). — DOI:10.1090/S0273-0979-1990-15918-X.
• Kirsten Eisenträger, Sean Hallgren, Kristin Lauter, Travis Morrison, Christophe Petit. Supersingular isogeny graphs and endomorphism rings: Reductions and solutions // Advances in Cryptology – EUROCRYPT 2018: 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29 - May 3, 2018, Proceedings, Part III / Jesper Buus Nielsen, Vincent Rijmen. — Cham : Springer, 2018. — Т. 10822. — С. 329–368. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-319-78372-7_11.
• 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. — 2013.
• Adam Marcus, Daniel Spielman, Nikhil Srivastava. Interlacing families IV: Bipartite Ramanujan graphs of all sizes // Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium. — 2015.
• Michael B. Cohen. Ramanujan Graphs in Polynomial Time // =Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium. — 2016. — DOI:10.1109/FOCS.2016.37.
• Guiliana Davidoff, Peter Sarnak, Alain Valette. Elementary number theory, group theory and Ramanjuan graphs. — Cambridge University Press, 2003. — Т. 55. — (LMS student texts) — ISBN 0-521-53143-8.
• Sunada T. L-functions in geometry and some applications // Lecture Notes in Math.. — 1985. — Т. 1201 (10 листопада). — С. 266–284. — (Lecture Notes in Mathematics). — ISBN 978-3-540-16770-9. — DOI:10.1007/BFb0075662.

Посилання

• Survey paper by M. Ram Murty Архівовано липень 6, 2011 на сайті Wayback Machine.