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

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

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

Определение

Пусть $G$ будет связным $d$-регулярным графом с $n$ вершинами и пусть ${\lambda }_0⩾{\lambda }_1⩾\cdots ⩾{\lambda }_{n-1}$ будут собственными числами матрицы смежности графа $G$. Поскольку граф $G$ связен и $d$-регулярен, его собственные числа удовлетворяют неравенствам $d={\lambda }_0>{\lambda }_1⩾\cdots ⩾{\lambda }_{n-1}⩾-d$. Если существует значение ${\lambda }_i$, для которого $|{\lambda }_i|<d$, определим

$\lambda (G)=\underset{|{\lambda }_i|<d}{\max }|{\lambda }_i|.$

$d$-Регулярный граф $G$ является графом Рамануджана, если $\lambda (G)⩽2\sqrt{d-1}$.

Граф Рамануджана описывается как регулярный граф, Шаблон:Не переведено 5 которого удовлетворяет аналогу гипотезы Римана.

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

Для фиксированного значения $d$ и большого $n$ $d$-регулярные графы Рамануджана с $n$ вершинами почти минимизируют $\lambda (G)$. Если $G$ является $d$-регулярным графом с диаметром $m$, теорема АлонаШаблон:Sfn утверждает

${\lambda }_1⩾2\sqrt{d-1}-\frac{2\sqrt{d-1}-1}{\lfloor m/2\rfloor }.$

Если $G$ является $d$-регулярным и связным по меньшей мере на трёх вершинах, $|{\lambda }_1|<d$, а потому $\lambda (G)⩾{\lambda }_1$. Пусть ${𝒢}_n^d$ будет множеством всех связных $d$-регулярных графов $G$ по меньшей мере с $n$ вершинами. Поскольку минимальный диаметр графа в ${𝒢}_n^d$ стремится к бесконечности при фиксированном $d$ и увеличивающемся $n$, из этой теоремы следует теорема Алона и Боппана, которая утверждает

$\underset{n\to \mathrm{\infty }}{\lim }\underset{G\in {𝒢}_n^d}{\inf }\lambda (G)⩾2\sqrt{d-1}.$

Чуть более строгая граница

${\lambda }_1⩾2\sqrt{d-1}\cdot (1-\frac{c}{m^2}),$

где $c\approx 2{\pi }^2$. Набросок доказательства Фридмана следующий. Возьмём $k=\lfloor \frac{m}{2}\rfloor -1$. Пусть $T_{d,k}$ будет $d$-регулярным деревом высоты $k$ и пусть $A_{T_k}$ будет его матрицей смежности. Мы хотим доказать, что $\lambda (G)⩾\lambda (T_{d,k})=2\sqrt{d-1}\cos \theta$ для некоторого $\theta$, зависящего только от $m$. Определим функцию $g:V(T_{d,k})\to ℝ$ следующим образом $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{array}{ccc}{c}_{1}g(v_s)& & dist(v,s)⩽k,\\ -c_{2}g(v_t)& & dist(v,t)⩽k,\\ 0& \end{array}$

где $v_s$ — вершина в $T_{d,k}$, расстояние от которой до корня равно расстоянию от $v$ до $s$ ($dist(v,s)$) и симметрично для $v_t$. Путём выбора подходящих $c_1,c_2$ мы получим $f\perp 1$, $(Af{)}_v⩾\lambda (T_{d,k})f_v$ для $v$ близких к $s$ и $(Af{)}_v⩽\lambda (T_{d,k})f_v$ для $v$ близких к $t$. Тогда по теореме о минимаксе $\lambda (G)⩾fA{f}^T/\Vert f{\Vert }^2⩾\lambda (T_{d,k})$.

Построения

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

• Лубоцки, Филлипс и СарнакШаблон:Sfn показали, как построить бесконечное семейство $(p+1)$-регулярных графов Рамануджана, когда $p$ является простым числом и $p\equiv 1(\mathrm{mod}4)$. Их доказательство использует гипотезу Рамануджана, откуда и получили название графы Рамануджана. Кроме свойства быть графами Рамануджана, их построение имеет ряд других свойств. Например, обхват равен $\mathrm{\Omega }({\log }_p(n))$, где $n$ равно числу узлов.
• МоргенштернШаблон:Sfn расширил построение Лубоцки, Филлипса и Сарнака. Его расширенное построение допустимо, если $p$ является степенью простого числа.
• Арнольд Пицер доказал, что Шаблон:Не переведено 5 являются графами Рамануджана, хотя, как правило, они имеют меньший обхват, чем графы Лубоцки, Филлипса и СарнакаШаблон:Sfn. Подобно графам Лубоцки, Филлипса и Сарнака, степени этих графов всегда равны простому числу + 1. Эти графы предлагаются в качестве базиса постквантовой эллиптической криптографииШаблон:Sfn.
• Адам Маркус, Даниэль Спильман и Никхил СриваставаШаблон:Sfn доказали существование $d$-регулярных двудольных графов Рамануджана для любого $d$. ПозднееШаблон:Sfn они доказали, что существуют двудольные графы Рамануджана любой степени и с любым числом вершин. Михаэль Б. КоэнШаблон:Sfn показал, каким образом строить эти графы за полиномиальное время.

Литература

• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья

Ссылки

• Survey paper by M. Ram Murty Шаблон:Wayback