Введение

В математической области теории спектральных графов граф Рамануджана — это регулярный граф, чей спектральный разрыв почти максимально возможен (см. экстремальную теорию графов). Такие графы являются превосходными спектральными расширителями. Как отмечается в обзоре Мурти, графы Рамануджана «объединяют различные области чистой математики, а именно теорию чисел, теорию представлений и алгебраическую геометрию». Эти графы названы в честь Шринивасы Рамануджана; их название происходит от гипотезы Рамануджана — Петерсона, которая была использована при построении некоторых из этих графов.

Определение

Пусть G — связный d-регулярный граф с n вершинами, и пусть λ — собственные значения матрицы смежности G (или спектр G). Поскольку G связен и d-регулярен, его собственные значения удовлетворяют условию |λ| ≤ d. Связный d-регулярный граф называется графом Рамануджана, если λ ≤ 2√d-1 для всех собственных значений λ, отличных от d. Многие источники используют альтернативное определение (когда существует λ такое, что λ = 2√d-1) для определения графов Рамануджана. Другими словами, мы допускаем значение 2√d-1 в дополнение к "малым" собственным значениям. Поскольку λ = d тогда и только тогда, когда граф является двудольным, мы будем называть графы, удовлетворяющие этому альтернативному определению, но не первому определению, двудольными графами Рамануджана. Если G — граф Рамануджана, то он также является двудольным графом Рамануджана, поэтому существование графов Рамануджана является более сильным условием. Как заметил Тошиказу Сунада, регулярный граф является графом Рамануджана тогда и только тогда, когда его дзета-функция Игары удовлетворяет аналогу гипотезы Римана.

Явные примеры

Полный граф имеет спектр, и таким образом, и граф является графом Рамануджана для каждого. Полный двудольный граф имеет спектр и, следовательно, является двудольным графом Рамануджана для каждого. Граф Петерсена имеет спектр, поэтому это 3-регулярный граф Рамануджана. Икосаэдрический граф — это 5-регулярный граф Рамануджана. Граф Палея порядка является -регулярным, при этом все остальные собственные значения равны , что делает графы Палея бесконечным семейством графов Рамануджана. В более общем случае, пусть будет многочленом степени 2 или 3 над полем. Пусть будет образом этого многочлена как мультимножеством, и предположим, что. Тогда граф Кейли для с генераторами из является графом Рамануджана. Математики часто заинтересованы в построении бесконечных семейств -регулярных графов Рамануджана для каждого фиксированного. Такие семейства полезны в приложениях.

Алгебраические конструкции

Несколько явных конструкций графов Рамануджана возникают как графы Кейли и носят алгебраический характер. См. обзор Винни Ли о гипотезе Рамануджана и других аспектах теории чисел, имеющих отношение к этим результатам. Любоцкий, Филлипс и Сарнак показали, как построить бесконечное семейство регулярных графов Рамануджана, когда *p* – простое число, и оба доказательства используют гипотезу Рамануджана, что и привело к названию графов Рамануджана. Помимо того, что это графы Рамануджана, эти конструкции удовлетворяют некоторым другим свойствам, например, их длина окружности равна *n*, где *n* – число вершин. Давайте схематично опишем конструкцию Любоцкого, Филлипса и Сарнака. Пусть *p* – простое число, не равное 5. По теореме Якоби о четырех квадратах, существует решений уравнения *x*² + *y*² + *z*² + *w*² = *p*, где *x* – нечетное, а *y*, *z*, *w* – четные. Каждому такому решению сопоставим матрицу. Если *p* не является квадратичным вычетом по модулю 8, то пусть Γ будет графом Кейли группы GL₂(ℤ/pℤ) с этими генераторами, а в противном случае, пусть Γ будет графом Кейли той же группы с теми же генераторами. Тогда Γ – *p*-регулярный граф на *p*² или *p*² - 1 вершинах, в зависимости от того, является ли *p* квадратичным вычетом по модулю 8. Доказано, что Γ – граф Рамануджана. Моргенштерн позднее расширил конструкцию Любоцкого, Филлипса и Сарнака. Его расширенная конструкция справедлива, когда *p* – степень простого числа. Арнольд Пизер доказал, что суперсингулярные изогенные графы являются графами Рамануджана, хотя они, как правило, имеют меньшую длину окружности, чем графы Любоцкого, Филлипса и Сарнака. Как и графы Любоцкого, Филлипса и Сарнака, степени вершин этих графов всегда равны простому числу плюс один.

Вероятностные примеры

Адам Маркус, Дэниел Спилман и Никил Шривастава доказали существование бесконечно многих регулярных двудольных графов Рамануджана для любого *k*. Позже они доказали, что существуют двудольные графы Рамануджана каждой степени и каждого числа вершин. Майкл Б. Коэн показал, как построить эти графы за полиномиальное время. Первоначальная работа основывалась на подходе Билу и Линиала. Они рассмотрели операцию, называемую 2-лифтом, которая принимает регулярный граф с *n* вершинами и знак на каждом ребре, и производит новый регулярный граф на 2*n* вершинах. Билу и Линиал предположили, что всегда существует такая расстановка знаков, чтобы модуль каждого нового собственного значения был не больше 2. Эта гипотеза гарантирует существование графов Рамануджана со степенью *k* и 2*n* вершинами для любого *n* – достаточно начать с полного графа *K<sub>n</sub>* и итеративно применять 2-лифты, сохраняющие свойство Рамануджана. Используя метод переплетения полиномов, Маркус, Спилман и Шривастава обобщили оригинальную работу Маркуса, Спилмана и Шриваставы на *r*-лифты. Остается открытым вопросом, существует ли бесконечно много регулярных (не двудольных) графов Рамануджана для любого *k*. В частности, проблема не решена для *k* = 4, наименьшего случая, для которого *k* не является степенью простого числа и, следовательно, не охватывается построением Моргенстерна.

Графы Рамануджана как графы расширителя

Постоянная в определении графов Рамануджана асимптотически остра. Более точно, оценка Алона-Боппаны утверждает, что для любых ε и k существует N такое, что все k-регулярные графы с не менее чем N вершинами удовлетворяют λ ≤ 2√k-1. Это означает, что графы Рамануджана по сути являются наилучшими возможными расширителями. Благодаря достижению точной границы для λ, лемма смешивания расширителей дает отличные оценки для равномерности распределения ребер в графах Рамануджана, и любое случайное блуждание на этих графах имеет логарифмическое время смешивания (относительно числа вершин): иными словами, случайное блуждание очень быстро сходится к (равномерному) стационарному распределению. Следовательно, диаметр графов Рамануджана также ограничен логарифмически относительно числа вершин.

Случайные графики

Подтверждая гипотезу Алона, Фридман показал, что многие семейства случайных графов слабо рамануджановы. Это означает, что для любых ε и δ и для достаточно больших n, случайный ε-регулярный граф с n вершинами удовлетворяет условию с высокой вероятностью. Хотя этот результат показывает, что случайные графы близки к рамануджановым, его нельзя использовать для доказательства существования графов Рамануджана. Тем не менее, предполагается, что случайные графы являются рамануджановыми с существенной вероятностью (примерно 52%). В дополнение к прямым численным доказательствам, существует некоторая теоретическая поддержка этой гипотезы: спектральный зазор ε-регулярного графа, по-видимому, ведет себя согласно распределению Трейси-Видома из теории случайных матриц, которое предсказывает ту же асимптотику.