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

В спектральной теории графов граф Рамануджана, названный по имени индийского математика Рамануджана, — это регулярный граф, спектральная щель^[англ.] которого почти настолько велика, насколько это возможно (см. статью «Экстремальная теория графов»). Такие графы являются прекрасными спектральными экспандерами.

Примерами графов Рамануджана служат клики, полные двудольные графы ${\displaystyle K_{n,n}}$ и граф Петерсена. Как замечает Мурти в обзорной статье Архивная копия от 6 июля 2011 на Wayback Machine, графы Рамануджана «сплавляют воедино различные ветви чистой математики, а именно, теорию чисел, теорию представлений и алгебраическую геометрию». Как заметил Тосикадзу Сунада, регулярный граф является графом Рамануджана тогда и только тогда, когда его дзета-функция Ихары^[англ.] удовлетворяет аналогу гипотезы Римана[1].

Определение

Пусть ${\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}}}$.

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

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

Для фиксированного значения ${\displaystyle d}$ и большого ${\displaystyle n}$ ${\displaystyle d}$-регулярные графы Рамануджана с ${\displaystyle n}$ вершинами почти минимизируют ${\displaystyle \lambda (G)}$. Если ${\displaystyle G}$ является ${\displaystyle d}$-регулярным графом с диаметром ${\displaystyle m}$, теорема Алона[2] утверждает

${\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})}$.

Построения

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

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

Примечания

1. Terras, 2011.
2. Nilli, 1991, с. 207–210.
3. Lubotzky, Phillips, Sarnak, 1988, с. 261–277.
4. Morgenstern, 1994, с. 44–62.
5. Pizer, 1990, с. 127–137.
6. Eisenträger, Hallgren, Lauter, Morrison, Petit, 2018, с. 329–368.
7. Немецкая фамилия и на немецком она должна звучать как Шпильман
8. Marcus, Spielman, Srivastava, 2013.
9. Marcus, Spielman, Srivastava, 2015.
10. 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. — С. 207–210. — doi:10.1016/0012-365X(91)90112-F.
• Alexander Lubotzky, Ralph Phillips, Peter Sarnak. Ramanujan graphs // Combinatorica. — 1988. — Т. 8, вып. 3. — 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. — doi:10.1006/jctb.1994.1054.
• Arnold K. Pizer. Ramanujan graphs and Hecke operators // Bulletin of the American Mathematical Society. — 1990. — Т. 23, вып. 1. — С. 127–137. — 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. — С. 266–284. — ISBN 978-3-540-16770-9. — doi:10.1007/BFb0075662.

Ссылки

• Survey paper by M. Ram Murty Архивная копия от 6 июля 2011 на Wayback Machine