# 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{{ safesubst:#invoke:Unsubst||$N=Dubious |date=__DATE__ |$B= {{#invoke:Category handler|main}}[dubious ] }}

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

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, 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

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.
• {{#invoke:citation/CS1|citation

|CitationClass=book }}

• {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

• {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

• {{#invoke:Citation/CS1|citation

|CitationClass=journal }}