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 , define

:

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, , 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" ≡ 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]