Ramanujan graph

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".

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 (see Spectral graph theory). Because G is connected and d-regular, its eigenvalues satisfy d = λ₀ > λ₁ $\geq \ldots \geq \lambda_{n-1} \geq -d$. Whenever there exists λ_i with | λ_i | < d, define

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

A d-regular graph G is a Ramanujan graph if λ(G) is defined and $\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 minimize λ(G). If G is a d-regular graph with diameter m, a theorem due to Nilli (pseudonym of Noga Alon) states

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

Whenever G is d-regular and connected on at least three vertices, | λ₁ | < 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

• 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; R. 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. 

External links

• Survey paper by M. Ram Murty