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

1 Definition
2 Extremality of Ramanujan graphs
3 Constructions
4 References
5 External links

[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 \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.

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