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 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 2{\sqrt {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 2{\sqrt {d-1}}-{\frac {2{\sqrt {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\to \infty }\inf _{G\in {\mathcal {G}}_{n}^{d}}\lambda (G)\geq 2{\sqrt {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

• Guiliana Davidoff (2003). Elementary number theory, group theory and Ramanjuan graphs. LMS student texts. Vol. 55. Cambridge University Press. ISBN 0-521-53143-8. OCLC 50253269. {{cite book}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)
• Alexander Lubotzky (1988). "Ramanujan graphs". Combinatorica. 8: 261–277. doi:10.1007/BF02126799. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)
• Moshe Morgenstern (1994). "Existence and Explicit Constructions of q+1 Regular Ramanujan Graphs for Every Prime Power q". J. Combinatorial Theory, Series B. 62: 44–62. doi:10.1006/jctb.1994.1054.

External links

• Survey paper by M. Ram Murty