Ramanujan graph

From Wikipedia, the free encyclopedia

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

Contents

[edit] 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 = \lambda_0 \geq \lambda_1 \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}.

[edit] 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 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, | λ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}.

[edit] 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.

[edit] References

  • Lubotzky, A.; Phillips, R.; Sarnak, P. Ramanujan graphs, Combinatorica 8 (1988), 261-277.
  • Morgenstern, Moshe. Existence and Explicit Constructions of q+1 Regular Ramanujan Graphs for Every Prime Power q, Journal of Combinatorial Theory, Series B 62 (1994), 44-62.

[edit] External links