WikiSort.ru - Не сортированное

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

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

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии. Проверить статью на грамматические и орфографические ошибки.