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

Прикладами графів Рамануджана є кліки, повні двочасткові графи  та граф Петерсена. Як зауважує Мурті, графи Рамануджана «сплавляють воєдино різні гілки чистої математики, а саме, теорію чисел, теорію представлень та алгебричну геометрію». Як зауважив Тосікадзу Сунада, регулярний граф є графом Рамануджана тоді й лише тоді, коли його   задовольняє аналогу гіпотези Рімана.

Визначення
Нехай  — зв'язний -регулярний графом із  вершинами, а  — власні числа матриці суміжності графа . Оскільки граф  зв'язний і -регулярний, його власні числа задовольняють нерівності . Якщо існує значення , для котрого , визначимо

: 

-Регулярний граф  є графом Рамануджана, якщо .

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

Екстремальність графів Рамануджана
Для фіксованого значення  і великого  -регулярні графи Рамануджана з  вершинами майже мінімізують . Якщо  є -регулярним графом із діаметром , теорема Алона стверджує

: 

Якщо  є -регулярним і зв'язним принаймні на трьох вершинах, , а тому . Нехай  — множина всіх зв'язних -регулярних графів  принаймні з  вершинами. Оскільки мінімальний діаметр графа в  прямує до нескінченності за фіксованого  і збільшення , з цієї теореми випливає теорема Алона й Боппана, яка стверджує

: 

Трохи строгіша межа

: 

де . Суть доведення Фрідмана така. Візьмемо . Нехай  — -регулярне дерево висоти , і  — його матриця суміжності. Ми хочемо довести, що  для деякого , що залежить тільки від . Визначимо функцію  так: , де  є відстанню від  до кореня . Вибираючи  близьким до , можна довести, що . Тепер нехай  і  — пара вершин на відстані  і визначимо

: 

де  — вершина в , відстань від якої до кореня дорівнює відстані від  до  () і симетрична для . Вибравши відповідні  ми отримаємо ,  для  близьких до  і  для  близьких до . Тоді, за теоремою про мінімакс, .

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

* Лубоцькі, Філіпс та Сарнак показали, як побудувати нескінченне сімейство -регулярних графів Рамануджана, коли  є простим числом і . Їхнє доведення використовує гіпотезу Рамануджана, звідки й отримали назву графи Рамануджана. Крім властивості бути графами Рамануджана, їхня побудова має низку інших властивостей. Наприклад, обхват дорівнює , де  — число вузлів.
* Моргенштерн розширив побудову Лубоцькі, Філліпса та Сарнака. Його побудова допустима, якщо  є степенем простого числа.
* Арнольд Піцер довів, що  є графами Рамануджана, хоча, як правило, вони мають менший обхват, ніж графи Лубоцькі, Філліпса та Сарнака. Подібно до графів Лубоцькі, Філіпса та Сарнака, степеня цих графів завжди дорівнюють простому числу + 1. Ці графи пропонуються як базис постквантової еліптичної криптографії.
* Адам Маркус, Даніель Спільман та Нікхіл Срівастава довели існування -регулярних двочасткових графів Рамануджана для будь-якого . Пізніше вони довели, що існують двочасткові графи Рамануджана будь-якого степеня та з будь-яким числом вершин. Міхаель Б. Коен показав, як будувати ці графи за поліноміальний час.

Примітки


Література

*
*
*
*
*
*
*
*
*
* 
*


Посилання

*  Survey paper by M. Ram Murty   




