Ramanujan graph

In spectral graph theory, 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". As observed by Toshikazu Sunada, a regular graph is Ramanujan if and only if its Ihara zeta function satisfies an analog of the Riemann hypothesis.

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$. Because $G$ is connected and $d$-regular, its eigenvalues satisfy $d=\lambda _{0}>\lambda _{1}$ $\geq \ldots \geq \lambda _{n-1}\geq -d$. Whenever there exists $\lambda _{i}$ with $|\lambda _{i}|<d$, define{{ safesubst:#invoke:Unsubst||$N=Dubious |date=__DATE__ |$B= {{#invoke:Category handler|main}} }}

$\lambda (G)=\max _{|\lambda _{i}|<d}|\lambda _{i}|.\,$

A $d$-regular graph $G$ is a Ramanujan graph if $\lambda (G)\leq 2{\sqrt {d-1}}$.

A Ramanujan graph is characterized as a regular graph whose Ihara zeta function satisfies an analogue of the Riemann Hypothesis.

Extremality of Ramanujan graphs

For a fixed $d$ and large $n$, the $d$-regular, $n$-vertex Ramanujan graphs nearly 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}{\lfloor m/2\rfloor }}.$

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

• {{#invoke:citation/CS1|citation

|CitationClass=book }}

• {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

• {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

• {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

External links

• Survey paper by M. Ram Murty