Ramanujan graphs

In spectral graph theory, a Ramanujan graph, named after Srinivasa Ramanujan, is a regular graph whose spectral gap is almost as large as possible (see extremal graph theory). Such graphs are excellent spectral expanders.

Examples of Ramanujan graphs include the clique, the biclique ${\displaystyle K_{n,n}}$, and the Petersen graph. As Murty's survey paper notes, Ramanujan graphs "fuse diverse branches of pure mathematics, namely, number theory, representation theory, and algebraic geometry". 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.

Let ${\displaystyle G}$ be a connected ${\displaystyle d}$-regular graph with ${\displaystyle n}$ vertices, and let ${\displaystyle \lambda _{0}\geq \lambda _{1}\geq \cdots \geq \lambda _{n-1}}$ be the eigenvalues of the adjacency matrix of ${\displaystyle G}$. Because ${\displaystyle G}$ is connected and ${\displaystyle d}$-regular, its eigenvalues satisfy ${\displaystyle d=\lambda _{0}>\lambda _{1}}$ ${\displaystyle \geq \cdots \geq \lambda _{n-1}\geq -d}$. Whenever there exists ${\displaystyle \lambda _{i}}$ with ${\displaystyle |\lambda _{i}|<d}$, define

...
Wikipedia