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

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

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

Ссылки

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