У спектральній теорії графів граф Рамануджана, названий на честь індійського математика Рамануджана, — це регулярний граф, якого майже настільки велика, наскільки це можливо (див. статтю «Екстремальна теорія графів»). Такі графи є чудовими спектральними експандерами.
Прикладами графів Рамануджана є кліки, повні двочасткові графи та граф Петерсена. Як зауважує Мурті, графи Рамануджана «сплавляють воєдино різні гілки чистої математики, а саме, теорію чисел, теорію представлень та алгебричну геометрію». Як зауважив Тосікадзу Сунада, регулярний граф є графом Рамануджана тоді й лише тоді, коли його задовольняє аналог гіпотези Рімана.
Визначення Нехай — зв'язний -регулярний графом із вершинами, а — власні числа матриці суміжності графа . Оскільки граф зв'язний і -регулярний, його власні числа задовольняють нерівності . Якщо існує значення , для котрого , визначимо
-Регулярний граф є графом Рамануджана, якщо .
Граф Рамануджана описується як регулярний граф, якого задовольняє аналог гіпотези Рімана.
Екстремальність графів Рамануджана Для фіксованого значення і великого -регулярні графи Рамануджана з вершинами майже мінімізують . Якщо є -регулярним графом із діаметром , теорема Алона стверджує
Якщо є -регулярним і зв'язним принаймні на трьох вершинах, , а тому . Нехай — множина всіх зв'язних -регулярних графів принаймні з вершинами. Оскільки мінімальний діаметр графа в прямує до нескінченності за фіксованого і збільшення , з цієї теореми випливає теорема Алона й Боппана, яка стверджує
Трохи строгіша межа
де . Суть доведення Фрідмана така. Візьмемо . Нехай — -регулярне дерево висоти , і — його матриця суміжності. Ми хочемо довести, що для деякого , що залежить тільки від . Визначимо функцію так: , де є відстанню від до кореня . Вибираючи близьким до , можна довести, що . Тепер нехай і — пара вершин на відстані і визначимо
де — вершина в , відстань від якої до кореня дорівнює відстані від до () і симетрична для . Вибравши відповідні ми отримаємо , для близьких до і для близьких до . Тоді, за теоремою про мінімакс, .
Побудови Побудови графів Рамануджана часто алгебричні.
Лубоцькі, Філіпс та Сарнак показали, як побудувати нескінченне сімейство -регулярних графів Рамануджана, коли є простим числом і . Їхнє доведення використовує гіпотезу Рамануджана, звідки й отримали назву графи Рамануджана. Крім властивості бути графами Рамануджана, їхня побудова має низку інших властивостей. Наприклад, обхват дорівнює , де — число вузлів. Моргенштерн розширив побудову Лубоцькі, Філліпса та Сарнака. Його побудова допустима, якщо є степенем простого числа. Арнольд Піцер довів, що є графами Рамануджана, хоча, як правило, вони мають менший обхват, ніж графи Лубоцькі, Філліпса та Сарнака. Подібно до графів Лубоцькі, Філіпса та Сарнака, степеня цих графів завжди дорівнюють простому числу + 1. Ці графи пропонуються як базис постквантової еліптичної криптографії. Адам Маркус, Даніель СпільманНімецьке прізвище і німецькою воно має звучати як Шпільман та Нікхіл Срівастава довели існування -регулярних двочасткових графів Рамануджана для будь-якого . Пізніше вони довели, що існують двочасткові графи Рамануджана будь-якого степеня та з будь-яким числом вершин. Міхаель Б. Коен показав, як будувати ці графи за поліноміальний час.
Примітки
Література
Посилання
Survey paper by M. Ram Murty