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

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

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

Определение

Пусть $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$ , теорема Алона^[2] утверждает

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

Построения

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

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

Примечания

↑ Terras, 2011.
↑ Nilli, 1991, с. 207–210.
↑ Lubotzky, Phillips, Sarnak, 1988, с. 261–277.
↑ Morgenstern, 1994, с. 44–62.
↑ Pizer, 1990, с. 127–137.
↑ Eisenträger, Hallgren, Lauter, Morrison, Petit, 2018, с. 329–368.
↑ Немецкая фамилия и на немецком она должна звучать как Шпильман
↑ Marcus, Spielman, Srivastava, 2013.
↑ Marcus, Spielman, Srivastava, 2015.
↑ 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.