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

$\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. Adam Marcus, Daniel Spielman and Nikhil Srivastava proved the existence of $d$-regular bipartite Ramanujan graphs for any $d$.

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.
• Adam Marcus; Daniel Spielman; Nikhil Srivastava (2013). "Interlacing families I: Bipartite Ramanujan graphs of all degrees". Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium.

External links

• Survey paper by M. Ram Murty