Canonical: https://knowlpedia.com/discrete-structures/ramanujan-graph/

# Ramanujan graph

A finite connected regular graph whose nontrivial adjacency eigenvalues lie in the tree spectral interval.

A finite connected undirected simple [graph](https://knowlpedia.com/discrete-structures/finite-graph/) of constant [degree](https://knowlpedia.com/discrete-structures/vertex-degree/) \(d\ge2\) is a **Ramanujan graph** if every [eigenvalue](https://knowlpedia.com/linear-algebra/eigenvalue/) \(\lambda\) of its adjacency matrix other than the trivial eigenvalues satisfies
\[
|\lambda|\le2\sqrt{d-1}.
\]
The adjacency matrix has entry \(1\) at adjacent vertex pairs and \(0\) elsewhere. The trivial eigenvalue is \(d\), together with \(-d\) when the graph is bipartite. Here bipartite means that the vertices split into two sets with every edge joining the two sets.

## Bipartite convention

The negative eigenvalue \(-d\) is excluded in the bipartite case. Consequently bipartite graphs can be Ramanujan; imposing the displayed bound on \(-d\) would rule them out for \(d>2\).

## Quaternionic constructions

The Lubotzky–Phillips–Sarnak construction produces arithmetic families of [Cayley graphs](https://knowlpedia.com/discrete-structures/cayley-graph/) from quaternionic data. The spectral estimate is a theorem about those constructions, not a property of an arbitrary Cayley graph.

## References

1. Adam W. Marcus, Daniel A. Spielman, and Nikhil Srivastava, *Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees*, [author-hosted paper](https://www.cs.yale.edu/homes/spielman/PAPERS/lifts.pdf), §2.1, p. 2.
