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

У спектральній теорії графів граф Рамануджана, названий на честь індійського математика Рамануджана, — це регулярний граф, спектральна щілина^[en] якого майже настільки велика, наскільки це можливо (див. статтю «Екстремальна теорія графів»). Такі графи є чудовими спектральними експандерами.

Прикладами графів Рамануджана є кліки, повні двочасткові графи ${\displaystyle K_{n,n}}$ та граф Петерсена. Як зауважує Мурті^[1], графи Рамануджана «сплавляють воєдино різні гілки чистої математики, а саме, теорію чисел, теорію представлень та алгебричну геометрію». Як зауважив Тосікадзу Сунада, регулярний граф є графом Рамануджана тоді й лише тоді, коли його дзета-функція Іхари^[en] задовольняє аналогу гіпотези Рімана^[2].

Визначення

Нехай ${\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}$, теорема Алона^[3] стверджує

${\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})}$.

Побудови

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

• Лубоцькі, Філіпс та Сарнак^[4] показали, як побудувати нескінченне сімейство ${\displaystyle (p+1)}$-регулярних графів Рамануджана, коли ${\displaystyle p}$ є простим числом і ${\displaystyle p\equiv 1{\pmod {4}}}$. Їхнє доведення використовує гіпотезу Рамануджана, звідки й отримали назву графи Рамануджана. Крім властивості бути графами Рамануджана, їхня побудова має низку інших властивостей. Наприклад, обхват дорівнює ${\displaystyle \Omega (\log _{p}(n))}$, де ${\displaystyle n}$ — число вузлів.
• Моргенштерн^[5] розширив побудову Лубоцькі, Філліпса та Сарнака. Його побудова допустима, якщо ${\displaystyle p}$ є степенем простого числа.
• Арнольд Піцер довів, що суперсингулярні ізогенії графа^[en] є графами Рамануджана, хоча, як правило, вони мають менший обхват, ніж графи Лубоцькі, Філліпса та Сарнака^[6]. Подібно до графів Лубоцькі, Філіпса та Сарнака, степеня цих графів завжди дорівнюють простому числу + 1. Ці графи пропонуються як базис постквантової еліптичної криптографії^[7].
• Адам Маркус, Даніель Спільман^[8] та Нікхіл Срівастава^[9] довели існування ${\displaystyle d}$-регулярних двочасткових графів Рамануджана для будь-якого ${\displaystyle d}$. Пізніше^[10] вони довели, що існують двочасткові графи Рамануджана будь-якого степеня та з будь-яким числом вершин. Міхаель Б. Коен^[11] показав, як будувати ці графи за поліноміальний час.