Ramanujan graph

From Free net encyclopedia

A Ramanujan graph 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 <math>K_{n,n}</math>, 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 External links

[edit]

Definition

Let <math>G</math> be a connected <math>d</math>-regular graph with <math>n</math> vertices, and let <math>\lambda_0 \geq \lambda_1 \geq \ldots \geq \lambda_{n-1}</math> be the eigenvalues of the adjacency matrix of <math>G</math> (see Spectral graph theory). Because <math>G</math> is connected and <math>d</math>-regular, its eigenvalues satisfy <math>d = \lambda_0 \geq \lambda_1 \geq \ldots \geq \lambda_{n-1} \geq -d </math>. Whenever there exists <math>\lambda_i</math> with <math>|\lambda_i| < d</math>, define

<math>\lambda(G) = \max_{|\lambda_i| < d} |\lambda_i|</math>.

A <math>d</math>-regular graph <math>G</math> is a Ramanujan graph if <math>\lambda(G)</math> is defined and <math>\lambda(G) \leq 2\sqrt{d-1}</math>.

[edit]

Extremality of Ramanujan graphs

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

<math>\lambda_1 \geq 2\sqrt{d-1} - \frac{2\sqrt{d-1} - 1}{m}</math>.

Whenever <math>G</math> is <math>d</math>-regular and connected on at least three vertices, <math>|\lambda_1| < d</math>, and therefore <math>\lambda(G) \geq \lambda_1</math>. Let <math>\mathcal{G}_n^d</math> be the set of all connected <math>d</math>-regular graphs <math>G</math> with at least <math>n</math> vertices. Because the minimum diameter of graphs in <math>\mathcal{G}_n^d</math> approaches infinity for fixed <math>d</math> and increasing <math>n</math>, Nilli's theorem implies an earlier theorem of Alon and Boppana which states

<math>\lim_{n \to \infty} \inf_{G \in \mathcal{G}_n^d} \lambda(G) \geq 2\sqrt{d-1}</math>.

[edit]

Constructions

Constructions of Ramanujan graphs are often algebraic. Lubotzky, Phillips, and Sarnak show how to construct an infinite family of <math>p+1</math>-regular Ramanujan graphs, whenever <math>p \equiv 1\mod 4</math> is a prime.

[edit]