Изменения

По теореме Алона (Alon) и Боппана (Boppana) для всех достаточно больших d-регулярных графов выполняется неравенство <tex>\lambda \geq geqslant 2{\sqrt {d-1}}-o(1)</tex>, где λ <tex>\lambda </tex> — второе по абсолютной величине собственное число[1]. Для графов Рамануджана[en]<tex>\lambda \leq leqslant 2{\sqrt {d-1}} [1]</tex>. Таким образом, графы Рамануджана имеют асимптотически наименьшее возможное значение λ и являются превосходными спектральными расширителями. Александр Любоцкий, Филипс и Сарнак (1988), Маргулис (1988) и Моргенштерн (1994) показали как можно явно сконструировать граф Рамануджана. По теореме Фридмана (Friedman,2003) случайный d-регулярный граф с <tex>n</tex> вершинами является почти графом Рамануджана, поскольку выполняется <tex> \lambda \leqslant 2\sqrt{d-1}+\epsilon</tex> с вероятностью <tex>1 - o(1)</tex> при <tex>n \to \infty</tex>.