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

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

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

Визначення

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

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

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

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

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

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

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

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

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

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

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

де $c\approx 2\pi ^{2}$. Суть доведення Фрідмана така. Візьмемо $k=\left\lfloor {\frac {m}{2}}\right\rfloor -1$. Нехай $T_{d,k}$ — $d$-регулярне дерево висоти $k$, і $A_{T_{k}}$ — його матриця суміжності. Ми хочемо довести, що $\lambda (G)\geqslant \lambda (T_{d,k})=2{\sqrt {d-1}}\cos \theta$ для деякого $\theta$, що залежить тільки від $m$. Визначимо функцію $g:V(T_{d,k})\rightarrow \mathbb {R}$ так: $g(x)=(d-1)^{-\delta /2}\cdot \sin((k+1-\delta )\theta )$, де $\delta$ є відстанню від $x$ до кореня $T_{d,k}$. Вибираючи $\theta$ близьким до $2\pi /m$, можна довести, що $A_{t,k}g=\lambda (T_{d,k})g$. Тепер нехай $s$ і $t$ — пара вершин на відстані $m$ і визначимо

$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}}$

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

Побудови

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

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

Література

• 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 (28 липня). — С. 207–210. — DOI:10.1016/0012-365X(91)90112-F.
• Alexander Lubotzky, Ralph Phillips, Peter Sarnak. Ramanujan graphs // Combinatorica. — 1988. — Т. 8, вип. 3 (28 липня). — 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 (28 липня). — DOI:10.1006/jctb.1994.1054.
• Arnold K. Pizer. Ramanujan graphs and Hecke operators // Bulletin of the American Mathematical Society. — 1990. — Т. 23, вип. 1 (28 липня). — С. 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 (28 липня). — С. 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.