Ramanujan graph

Ramanujan graph --- граф Рамануджана.

1. A finite regular graph of degree [math]\displaystyle{ k }[/math] is said to be a Ramanujan graph if, apart from the trivial eigenvalues [math]\displaystyle{ \pm k }[/math], its spectrum is contained not only in [math]\displaystyle{ [-k,k] }[/math] as Perron--Frobenius guarantees, but in the smaller range [math]\displaystyle{ [-2\sqrt{k-1}, 2\sqrt{k-1}] }[/math]. This range is in some asymptotic sense the smallest possible.

2. A [math]\displaystyle{ k }[/math]-regular graph [math]\displaystyle{ X }[/math] is a Ramanujan graph if and only if its Ihara zeta function [math]\displaystyle{ Z_{X}(s) }[/math] satisfies the Riemann hypothesis, i.e., all poles of [math]\displaystyle{ Z_{X}(s) }[/math] in [math]\displaystyle{ 0 \lt \Re s \lt 1 }[/math] lie on the line [math]\displaystyle{ \Re s = \frac{1}{2} }[/math].