# Ramanujan graph

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 $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.[1]

## Definition

Let $G$ be a connected $d$-regular graph with $n$ vertices, and let $\lambda_0 \geq \lambda_1 \geq \ldots \geq \lambda_{n-1}$ be the eigenvalues of the adjacency matrix of $G$. Because $G$ is connected and $d$-regular, its eigenvalues satisfy $d = \lambda_0 > \lambda_1$ $\geq \ldots \geq \lambda_{n-1} \geq -d$. Whenever there exists $\lambda_i$ with $|\lambda_i| < d$, define[dubious ]

$\lambda(G) = \max_{|\lambda_i| < d} |\lambda_i|.\,$

A $d$-regular graph $G$ is a Ramanujan graph if $\lambda(G) \leq 2\sqrt{d-1}$.

A Ramanujan graph is characterized as a regular graph whose Ihara zeta function satisfies an analogue of the Riemann Hypothesis.

## Extremality of Ramanujan graphs

For a fixed $d$ and large $n$, the $d$-regular, $n$-vertex Ramanujan graphs nearly minimize $\lambda(G)$. If $G$ is a $d$-regular graph with diameter $m$, a theorem due to Nilli[2] states

$\lambda_1 \geq 2\sqrt{d-1} - \frac{2\sqrt{d-1} - 1}{\lfloor m/2\rfloor}.$

Whenever $G$ is $d$-regular and connected on at least three vertices, $|\lambda_1| < d$, and therefore $\lambda(G) \geq \lambda_1$. Let $\mathcal{G}_n^d$ be the set of all connected $d$-regular graphs $G$ with at least $n$ vertices. Because the minimum diameter of graphs in $\mathcal{G}_n^d$ approaches infinity for fixed $d$ and increasing $n$, Nilli's theorem implies an earlier theorem of Alon and Boppana which states

$\lim_{n \to \infty} \inf_{G \in \mathcal{G}_n^d} \lambda(G) \geq 2\sqrt{d-1}.$

## Constructions

Constructions of Ramanujan graphs are often algebraic. Lubotzky, Phillips and Sarnak show how to construct an infinite family of p +1-regular Ramanujan graphs, whenever p ≡ 1 (mod 4) is a prime. Their proof uses the Ramanujan conjecture, which led to the name of Ramanujan graphs. Morgenstern extended the construction of Lubotzky, Phillips and Sarnak to all prime powers.

## References

1. ^ Audrey Terras, Zeta Functions of Graphs: A Stroll through the Garden, volume 128, Cambridge Studies in Advanced Mathematics, Cambridge University Press, (2010).
2. ^ A Nilli, On the second eigenualue of a graph, Discrete Mathematics 91 (1991) pp. 207-210.
• Guiliana Davidoff; Peter Sarnak; Alain Valette (2003). Elementary number theory, group theory and Ramanjuan graphs. LMS student texts 55. Cambridge University Press. ISBN 0-521-53143-8. OCLC 50253269.
• Alexander Lubotzky; Ralph Phillips; Peter Sarnak (1988). "Ramanujan graphs". Combinatorica 8 (3): 261–277. doi:10.1007/BF02126799.
• Moshe Morgenstern (1994). "Existence and Explicit Constructions of q+1 Regular Ramanujan Graphs for Every Prime Power q". J. Combinatorial Theory, Series B 62: 44–62. doi:10.1006/jctb.1994.1054.
• T. Sunada (1985). "L-functions in geometry and some applications". Lecture Notes in Math. Lecture Notes in Mathematics 1201: 266–284. doi:10.1007/BFb0075662. ISBN 978-3-540-16770-9.