As Murty's survey paper[1] 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.
[3] Mathematicians are often interested in constructing infinite families of
See Winnie Li's survey on Ramanujan's conjecture and other aspects of number theory relevant to these results.
[5] Lubotzky, Phillips and Sarnak[2] and independently Margulis[6] showed how to construct an infinite family of
Besides being Ramanujan graphs, these constructions satisfies some other properties, for example, their girth is
Morgenstern[7] later extended the construction of Lubotzky, Phillips and Sarnak.
Arnold Pizer proved that the supersingular isogeny graphs are Ramanujan, although they tend to have lower girth than the graphs of Lubotzky, Phillips, and Sarnak.
Adam Marcus, Daniel Spielman and Nikhil Srivastava[9] proved the existence of infinitely many
Later[10] they proved that there exist bipartite Ramanujan graphs of every degree and every number of vertices.
Michael B. Cohen[11] showed how to construct these graphs in polynomial time.
The initial work followed an approach of Bilu and Linial.
Bilu & Linial conjectured that there always exists a signing so that every new eigenvalue of
This conjecture guarantees the existence of Ramanujan graphs with degree
, and iteratively take 2-lifts that retain the Ramanujan property.
Using the method of interlacing polynomials, Marcus, Spielman, and Srivastava[9] proved Bilu & Linial's conjecture holds when
is already a bipartite Ramanujan graph, which is enough to conclude the existence result.
The sequel[10] proved the stronger statement that a sum of
random bipartite matchings is Ramanujan with non-vanishing probability.
Hall, Puder and Sawin[12] extended the original work of Marcus, Spielman and Srivastava to r-lifts.
is not a prime power and hence not covered by Morgenstern's construction.
in the definition of Ramanujan graphs is asymptotically sharp.
, the expander mixing lemma gives excellent bounds on the uniformity of the distribution of the edges in Ramanujan graphs, and any random walks on the graphs has a logarithmic mixing time (in terms of the number of vertices): in other words, the random walk converges to the (uniform) stationary distribution very quickly.
Therefore, the diameter of Ramanujan graphs are also bounded logarithmically in terms of the number of vertices.
Confirming a conjecture of Alon, Friedman[13] showed that many families of random graphs are weakly-Ramanujan.
It is conjectured,[14] though, that random graphs are Ramanujan with substantial probability (roughly 52%).
In addition to direct numerical evidence, there is some theoretical support for this conjecture: the spectral gap of a
-regular graph seems to behave according to a Tracy-Widom distribution from random matrix theory, which would predict the same asymptotic.
Expander graphs have many applications to computer science, number theory, and group theory, see e.g Lubotzky's survey on applications to pure and applied math and Hoory, Linial, and Wigderson's survey which focuses on computer science.
Importantly, the Lubotzky, Phillips, and Sarnak graphs can be traversed extremely quickly in practice, so they are practical for applications.