Изменения

Нетрудно понять, что граф Кэли <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>2{\sqrt{p}}</tex>, т.е. мы получили граф Рамануджана.

===Коды, исправляющие ошибки===

С помощью расширяющего графа можно посторить линейный код, позволяющий исправлять ошибки в доле <tex>\delta = 1/(2000d)</tex> битов. Чтобы задать линейный код с длиной кодового слова n, достаточно описать его проверочную матрицу <tex>H</tex> <tex>(</tex>слово <tex>x \in \{0, 1\}^n</tex> является кодовым словом если и только если <tex>Hx^t = 0)</tex>. Другими словами, нужно задать систему линейных уравнений для переменных <tex>x_1, . . . , x_n;</tex> решения этой системы и будут кодовыми словами.