Изменения

<tex>{{Теорема|statement=[[Основные определения теории графов#Часто используемые графы|d</tex>-регулярный граф ]] называется графом Рамануджана, если его второе по модулю собственное число не превосходит <tex>\lambda \leq 2{\sqrt {d-1}}</tex>. Любоцкий, Сарнак, Филлипс и Маргулис указали явную конструкцию графов Кэли, являющихся графами Рамануджана. Опишем эту конструкцию.Пусть <tex>p</tex> и <tex>q</tex> простые числа, <tex>p = 1 \bmod 4</tex> и <tex>q = - o(1 \bmod 4</tex>. В качестве группы <tex>G</tex> возьмём <tex>PGL(2, \mathbb Z/q{\mathbb Z})</tex>, т.е. невырожденные матрицы 2 × 2 над полем вычетов по модулю <tex>q</tex>, профакторизованные по отношению пропорциональности (с обычной операцией матричного умножения).Далее мы зададим в этой группе симметричное множество <tex>S</tex>. Выберем такое целое <tex>i</tex>, что <tex>i^2 = −1 \bmod q</tex>. Можно доказать, что тогда имеется ровно <tex>(p + 1)</tex> целочисленное решение уравнения}}

'''Замечание:''' случайный [[Основные определения теории графов#Часто используемые графы|d-регулярный граф]] с <tex>a_0^2 + a_1^2 + a_3^2 = p</tex> такое, что <tex>a_0</tex> положительно и нечётно, а <tex>a_1n</tex>вершинами почти является графом Рамануджана, так как выполняется неравенство <tex>a_2</tex>, <tex>a_3</tex> чётны. Каждой такой четвёрке сопоставим матрицу <tex>A = \begin{pmatrix} a_0 + ia_1 & a_2 + ia_3lambda \leq 2\ sqrt {d-a_2 1} + ia_3 & a_0 - ia_1 \end{pmatrix}epsilon</tex> Эти матрицы образуют множество S.Нетрудно понять, что граф Кэли с вероятностью <tex>1 - o(G, S1)</tex> состоит из при <tex>n \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>2{to \sqrt{p}}inf</tex>, т.е. мы получили граф Рамануджана.