# 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 ${\displaystyle 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.[1]

## Definition

Let ${\displaystyle G}$ be a connected ${\displaystyle d}$-regular graph with ${\displaystyle n}$ vertices, and let ${\displaystyle \lambda _{0}\geq \lambda _{1}\geq \cdots \geq \lambda _{n-1}}$ be the eigenvalues of the adjacency matrix of ${\displaystyle G}$. Because ${\displaystyle G}$ is connected and ${\displaystyle d}$-regular, its eigenvalues satisfy ${\displaystyle d=\lambda _{0}>\lambda _{1}}$ ${\displaystyle \geq \cdots \geq \lambda _{n-1}\geq -d}$. Whenever there exists ${\displaystyle \lambda _{i}}$ with ${\displaystyle |\lambda _{i}|, define

${\displaystyle \lambda (G)=\max _{|\lambda _{i}|

A ${\displaystyle d}$-regular graph ${\displaystyle G}$ is a Ramanujan graph if ${\displaystyle \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 ${\displaystyle d}$ and large ${\displaystyle n}$, the ${\displaystyle d}$-regular, ${\displaystyle n}$-vertex Ramanujan graphs nearly minimize ${\displaystyle \lambda (G)}$. If ${\displaystyle G}$ is a ${\displaystyle d}$-regular graph with diameter ${\displaystyle m}$, a theorem due to Nilli[2] states

${\displaystyle \lambda _{1}\geq 2{\sqrt {d-1}}-{\frac {2{\sqrt {d-1}}-1}{\lfloor m/2\rfloor }}.}$

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

${\displaystyle \lim _{n\to \infty }\inf _{G\in {\mathcal {G}}_{n}^{d}}\lambda (G)\geq 2{\sqrt {d-1}}.}$

A slightly stronger bound is

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

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

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

## Constructions

Constructions of Ramanujan graphs are often algebraic.

• Lubotzky, Phillips and Sarnak[3] show how to construct an infinite family of ${\displaystyle (p+1)}$-regular Ramanujan graphs, whenever ${\displaystyle p}$ is a prime number and ${\displaystyle p\equiv 1{\pmod {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 ${\displaystyle \Omega (\log _{p}(n))}$ where ${\displaystyle n}$ is the number of nodes.
• Morgenstern[4] extended the construction of Lubotzky, Phillips and Sarnak. His extended construction holds whenever ${\displaystyle p}$ is a prime power.
• Adam Marcus, Daniel Spielman and Nikhil Srivastava[5] proved the existence of ${\displaystyle d}$-regular bipartite Ramanujan graphs for any ${\displaystyle d}$. Later[6] they proved that there exist bipartite Ramanujan graphs of every degree and every number of vertices. Michael B. Cohen[7] showed how to construct these graphs in polynomial time.

## References

1. ^ Audrey Terras, Zeta Functions of Graphs: A Stroll through the Garden, volume 128, Cambridge Studies in Advanced Mathematics, Cambridge University Press, (2010).
2. ^ A Nilli, On the second eigenualue of a graph, Discrete Mathematics 91 (1991) pp. 207-210.
3. ^ Alexander Lubotzky; Ralph Phillips; Peter Sarnak (1988). "Ramanujan graphs". Combinatorica. 8 (3): 261–277. doi:10.1007/BF02126799.
4. ^ Moshe Morgenstern (1994). "Existence and Explicit Constructions of q+1 Regular Ramanujan Graphs for Every Prime Power q". Journal of Combinatorial Theory, Series B. 62: 44–62. doi:10.1006/jctb.1994.1054.
5. ^ Adam Marcus; Daniel Spielman; Nikhil Srivastava (2013). Interlacing families I: Bipartite Ramanujan graphs of all degrees. Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium.
6. ^ Adam Marcus; Daniel Spielman; Nikhil Srivastava (2015). Interlacing families IV: Bipartite Ramanujan graphs of all sizes. Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium.
7. ^ Michael B. Cohen (2016). Ramanujan Graphs in Polynomial Time. Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium. doi:10.1109/FOCS.2016.37.