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 [http://www.mast.queensu.ca/~murty/ramanujan.pdf 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 = lambda_0 geq 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) is defined and $$lambda(G) leq 2sqrt{d-1}.

Extremality of Ramanujan graphs

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

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

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 o infty} inf_{G in mathcal{G}_n^d} lambda(G) geq 2sqrt{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" &equiv; 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

*
*
*

External links

* [http://www.mast.queensu.ca/~murty/ramanujan.pdf Survey paper by M. Ram Murty]