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

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

Прикладами графів Рамануджана є кліки, повні двочасткові графи $K_{n,n}$ та граф Петерсена. Як зауважує Мурті, графи Рамануджана «сплавляють воєдино різні гілки чистої математики, а саме, теорію чисел, теорію представлень та алгебричну геометрію». Як зауважив Тосікадзу Сунада, регулярний граф є графом Рамануджана тоді й лише тоді, коли його Шаблон:Не перекладено задовольняє аналогу гіпотези РіманаШаблон: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}$.

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

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

Для фіксованого значення $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$ є степенем простого числа.
• Арнольд Піцер довів, що Шаблон:Не перекладено є графами Рамануджана, хоча, як правило, вони мають менший обхват, ніж графи Лубоцькі, Філліпса та СарнакаШаблон:Sfn. Подібно до графів Лубоцькі, Філіпса та Сарнака, степеня цих графів завжди дорівнюють простому числу + 1. Ці графи пропонуються як базис постквантової еліптичної криптографіїШаблон:Sfn.
• Адам Маркус, Даніель Спільман та Нікхіл СріваставаШаблон:Sfn довели існування $d$-регулярних двочасткових графів Рамануджана для будь-якого $d$. ПізнішеШаблон:Sfn вони довели, що існують двочасткові графи Рамануджана будь-якого степеня та з будь-яким числом вершин. Міхаель Б. КоенШаблон:Sfn показав, як будувати ці графи за поліноміальний час.

Література

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

Посилання

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