Editing Ramanujan graph (section)

==Definition==

Let <math>G</math> be a connected <math>d</math>-regular graph with <math>n</math> vertices, and let <math>\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n</math> be the [[eigenvalues]] of the [[adjacency matrix]] of <math>G</math> (or the [[Spectral graph theory|spectrum]] of <math>G</math>). Because <math>G</math> is connected and <math>d</math>-regular, its eigenvalues satisfy <math>d = \lambda_1 > \lambda_2 </math> <math> \geq \cdots \geq \lambda_n \geq -d </math>.

Define <math>\lambda(G) = \max_{i\neq 1}|\lambda_i| = \max(|\lambda_2|,\ldots, |\lambda_n|)</math>. A connected <math>d</math>-regular graph <math>G</math> is a ''Ramanujan graph'' if <math>\lambda(G) \leq 2\sqrt{d-1}</math>.

Many sources uses an alternative definition <math>\lambda'(G) = \max_{|\lambda_i| < d} |\lambda_i|</math> (whenever there exists <math>\lambda_i</math> with <math>|\lambda_i| < d</math>) to define Ramanujan graphs.<ref name="lps88">{{cite journal|author=Alexander Lubotzky|author2=Ralph Phillips|author3=Peter Sarnak|year=1988|title=Ramanujan graphs|journal=Combinatorica|volume=8|issue=3|pages=261–277|doi=10.1007/BF02126799|s2cid=206812625}}</ref> In other words, we allow <math>-d</math> in addition to the "small" eigenvalues. Since <math>\lambda_n = -d</math> if and only if the graph is [[Bipartite graph|bipartite]], we will refer to the graphs that satisfy this alternative definition but not the first definition ''bipartite Ramanujan graphs''. If <math>G</math> is a Ramanujan graph, then <math>G \times K_2</math> is a bipartite Ramanujan graph, so the existence of Ramanujan graphs is stronger.

As observed by [[Toshikazu Sunada]], a regular graph is Ramanujan if and only if its [[Ihara zeta function]] satisfies an analog of the [[Riemann hypothesis]].<ref>{{citation|last=Terras|first=Audrey|title=Zeta functions of graphs: A stroll through the garden|volume=128|year=2011|series=Cambridge Studies in Advanced Mathematics|publisher=Cambridge University Press|isbn=978-0-521-11367-0|mr=2768284|authorlink=Audrey Terras}}</ref>