===Граф Рамануджана===
По теореме Алона (Alon) и Боппана (Boppana) для всех достаточно больших <tex>d</tex>-регулярных графов выполняется неравенство регулярный граф называется графом Рамануджана, если его второе по модулю собственное число не превосходит <tex>\lambda \geqslant 2{\sqrt {d-1}}-o(</tex>. Любоцкий, Сарнак, Филлипс и Маргулис указали явную конструкцию графов Кэли, являющихся графами Рамануджана. Опишем эту конструкцию.Пусть <tex>p</tex> и <tex>q</tex> простые числа, <tex>p = 1</tex> <tex>mod</tex> <tex>4</tex> и <tex>q = 1)</tex>, где <tex>\lambda mod</tex> <tex>4</tex> — второе по абсолютной величине собственное число. Для графов Рамануджана В качестве группы <tex>G</tex> возьмём <tex>PGL(2, \lambda \leqslant 2mathbb Z/q{\sqrt {d-1}mathbb Z})</tex>, т.е. невырожденные матрицы 2 × 2 над полем вычетов по модулю <tex>q</tex>, профакторизованные по отношению пропорциональности (с обычной операцией матричного умножения).Далее мы зададим в этой группе симметричное множество <tex>S</tex>. Таким образомВыберем такое целое <tex>i</tex>, графы Рамануджана имеют асимптотически наименьшее возможное значение λ и являются превосходными спектральными расширителямичто <tex>i^2 = −1</tex> <tex>mod</tex> <tex>q</tex>.Можно доказать, что тогда имеется ровно <tex>(p + 1)</tex> целочисленное решение уравнения
Александр Любоцкий, Филипс и Сарнак (1988), Маргулис (1988) и Моргенштерн (1994) показали как можно явно сконструировать граф Рамануджана. По теореме Фридмана (Friedman,2003) случайный d-регулярный граф с <tex>na_0^2 + a_1^2 + a_3^2 = p</tex> вершинами является почти графом Рамануджана, поскольку выполняется
такое, что <tex> \lambda \leqslant 2\sqrt{d-1}+\epsilona_0</tex>положительно и нечётно, а <tex>a_1</tex>, <tex>a_2</tex>, <tex>a_3</tex> чётны. Каждой такой четвёрке сопоставим матрицу
с вероятностью <tex>1 A = \begin{pmatrix} a_0 + ia_1 & a_2 + ia_3\\ -a_2 + ia_3 & a_0 - oia_1 \end{pmatrix}</tex> Эти матрицы образуют множество S.Нетрудно понять, что граф Кэли <tex>(G, S)</tex> состоит из <tex>\Theta(q^3)</tex> вершин, и степень каждой вершины равна <tex>(p + 1)</tex> при . Свойства данного графа зависят от соотношения <tex>p</tex> и <tex>q</tex>. Рассмотрим случай, когда p является квадратичным вычетом по модулю <tex>q</tex>. Тогда полученный граф Кэли состоит из двух связных компонент (поскольку все матрицы из <tex>S</tex> лежат в подгруппе <tex>G</tex> индекса два — подгруппе матриц, определитель которых является квадратичным вычетом). Обозначим <tex>X^{p,q}</tex> связную компоненту полученного графа. Можно доказать, что у <tex>X^{p,q}</tex> второе по абсолютной величине собственное число не превосходит <tex>n \to 2{\inftysqrt{p}}</tex>, т.е. мы получили граф Рамануджана.
==Приложения и полезные свойства==
