# 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 , 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 be a connected -regular graph with vertices, and let be the eigenvalues of the adjacency matrix of . Because is connected and -regular, its eigenvalues satisfy . Whenever there exists with , define{{ safesubst:#invoke:Unsubst||$N=Dubious |date=__DATE__ |$B=
{{#invoke:Category handler|main}}^{[dubious – discuss]}
}}

A -regular graph is a Ramanujan graph if .

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 and large , the -regular, -vertex Ramanujan graphs nearly minimize . If is a -regular graph with diameter , a theorem due to Nilli^{[2]} states

Whenever is -regular and connected on at least three vertices, , and therefore . Let be the set of all connected -regular graphs with at least vertices. Because the minimum diameter of graphs in approaches infinity for fixed and increasing , Nilli's theorem implies an earlier theorem of Alon and Boppana which states

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

- ↑ Audrey Terras,
*Zeta Functions of Graphs: A Stroll through the Garden*, volume 128, Cambridge Studies in Advanced Mathematics, Cambridge University Press, (2010). - ↑ 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 }}