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

## Constructions

Constructions of Ramanujan graphs are often algebraic.

• Lubotzky and 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(\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 ${\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.

## 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". J. 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.