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

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

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

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

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

Для фиксированного значения ${\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}$ является степенью простого числа.
• Арнольд Пицер доказал, что суперсингулярные изогении графа^[en] являются графами Рамануджана, хотя, как правило, они имеют меньший обхват, чем графы Лубоцки, Филлипса и Сарнака^[5]. Подобно графам Лубоцки, Филлипса и Сарнака, степени этих графов всегда равны простому числу + 1. Эти графы предлагаются в качестве базиса постквантовой эллиптической криптографии^[6].
• Адам Маркус, Даниэль Спильман^[7] и Никхил Сривастава^[8] доказали существование ${\displaystyle d}$-регулярных двудольных графов Рамануджана для любого ${\displaystyle d}$. Позднее^[9] они доказали, что существуют двудольные графы Рамануджана любой степени и с любым числом вершин. Михаэль Б. Коэн^[10] показал, каким образом строить эти графы за полиномиальное время.

Примечания

Литература

Ссылки

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

Эта страница в последний раз была отредактирована 28 марта 2022 в 11:35.