Interested Article - Граф Рамануджана

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

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

Определение

Пусть $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$ . Позднее они доказали, что существуют двудольные графы Рамануджана любой степени и с любым числом вершин. Михаэль Б. Коэн показал, каким образом строить эти графы за полиномиальное время.

Примечания

.
, с. 207–210.
, с. 261–277.
, с. 44–62.
, с. 127–137.
, с. 329–368.
Немецкая фамилия и на немецком она должна звучать как Шпильман
.
.
.

Литература

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 : .
Alexander Lubotzky, Ralph Phillips, Peter Sarnak. Ramanujan graphs // Combinatorica. — 1988. — Т. 8 , вып. 3 . — doi : .
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 : .
Arnold K. Pizer. Ramanujan graphs and Hecke operators // Bulletin of the American Mathematical Society. — 1990. — Т. 23 , вып. 1 . — С. 127–137 . — doi : .
Kirsten Eisenträger, Sean Hallgren, Kristin Lauter, Travis Morrison, Christophe Petit. // 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 : .
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 : .
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 : .