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

$\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}}.$

A slightly stronger bound is

$\lambda _{1}\geq 2{\sqrt {d-1}}\cdot \left(1-{\frac {c}{m^{2}}}\right)$,

where $c\approx 2\pi ^{2}$. The outline of Friedman's proof is the following. Take $k=\left\lfloor {\frac {m}{2}}\right\rfloor -1$. Let $T_{d,k}$ be the $d$-regular tree of height $k$ and let $A_{T_{k}}$ be its adjacency matrix. We want to prove that $\lambda (G)\geq \lambda (T_{d,k})=2{\sqrt {d-1}}\cos \theta$, for some $\theta$ depending only on $m$. Define a function $g:V(T_{d,k})\rightarrow \mathbb {R}$ by $g(x)=(d-1)^{-\delta /2}\cdot \sin((k+1-\delta )\theta )$, where $\delta$ is the distance from $x$ to the root of $T_{d,k}$. Choosing a $\theta$ close to $2\pi /m$ it can be proved that $A_{t,k}g=\lambda (T_{d,k})g$. Now let $s$ and $t$ be a pair of vertices at distance $m$ and define

$f(v)={\begin{cases}c_{1}g(v_{s})&{\text{for }}v{\text{ at distance }}\leq k{\text{ from }}s\\-c_{2}g(v_{t})&{\text{ for }}v{\text{ at distance }}\leq k{\text{ from }}t\\0&{\text{otherwise}}\end{cases}}$,

where $v_{s}$ is a vertex in $T_{d,k}$ which distance to the root is equal to the distance from $v$ to $s$ and the symmetric for $v_{t}$. By choosing properly $c_{1},c_{2}$ we get $f\perp 1$, $(Af)_{v}\geq \lambda (T_{d,k})f_{v}$ for $v$ close to $s$ and $(Af)_{v}\leq \lambda (T_{d,k})f_{v}$ for $v$ close to $t$. Then by the min-max theorem $\lambda (G)\geq fAf^{T}/||f||^{2}\geq \lambda (T_{d,k})$.

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$ is a prime number and $p\equiv 1(\mod 4)$. Their proof uses the Ramanujan conjecture, which led to the name of Ramanujan graphs. Besides being Ramanujan graphs, their construction satisfies some other properties, for example, their girth is $\Omega (\log _{p}(n))$ where $n$ is the number of nodes.
• Morgenstern extended the construction of Lubotzky, Phillips and Sarnak. His extended construction holds whenever $p$ is a prime power.
• Adam Marcus, Daniel Spielman and Nikhil Srivastava proved the existence of $d$-regular bipartite Ramanujan graphs for any $d$. Later they proved that there exist bipartite Ramanujan graphs of every degree and every number of vertices.

References

• Guiliana Davidoff; Peter Sarnak; Alain Valette (2003). Elementary number theory, group theory and Ramanjuan graphs. LMS student texts. Vol. 55. Cambridge University Press. ISBN 0-521-53143-8. OCLC 50253269.
• T. Sunada (1985). "L-functions in geometry and some applications". Lecture Notes in Math. Lecture Notes in Mathematics. 1201: 266–284. doi:10.1007/BFb0075662. ISBN 978-3-540-16770-9.

External links

• Survey paper by M. Ram Murty