Ramanujan graph - Knowlpedia

A finite connected undirected simple graph of constant degree $d\ge2$ is a Ramanujan graph if every 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 from quaternionic data. The spectral estimate is a theorem about those constructions, not a property of an arbitrary Cayley graph.

References

Adam W. Marcus, Daniel A. Spielman, and Nikhil Srivastava, Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees, author-hosted paper, §2.1, p. 2.