Ramanujan graph

In spectral graph theory, a Ramanujan graph, is a regular graph whose spectral gap is almost as large as possible (see extremal graph theory). Such graphs are excellent spectral expanders. As Murty's survey paper notes, Ramanujan graphs "fuse diverse branches of pure mathematics, namely, number theory, representation theory, and algebraic geometry". 
These graphs are indirectly named after Srinivasa Ramanujan; their name comes from the Ramanujan–Petersson conjecture, which was used in a construction of some of these graphs.
Definition.
Let formula_1 be a connected formula_2-regular graph with formula_3 vertices, and let formula_4 be the eigenvalues of the adjacency matrix of formula_1 (or the spectrum of formula_1). Because formula_1 is connected and formula_2-regular, its eigenvalues satisfy formula_9 formula_10. 
Define formula_11. A connected formula_2-regular graph formula_1 is a "Ramanujan graph" if formula_14.
Many sources uses an alternative definition formula_15 (whenever there exists formula_16 with formula_17) to define Ramanujan graphs. In other words, we allow formula_18 in addition to the "small" eigenvalues. Since formula_19 if and only if the graph is bipartite, we will refer to the graphs that satisfy this alternative definition but not the first definition "bipartite Ramanujan graphs". 
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.
Examples and constructions.
The complete graph formula_20 has spectrum formula_21, and thus formula_22 and the graph is a Ramanujan graph for every formula_23. The complete bipartite graph formula_24 has spectrum formula_25 and hence is a bipartite Ramanujan graph for every formula_2.
The Petersen graph has spectrum formula_27, so it is a 3-regular Ramanujan graph. The icosahedral graph is a 5-regular Ramanujan graph.
A Paley graph of order formula_28 is formula_29-regular with all other eigenvalues being formula_30, making Paley graphs an infinite family of Ramanujan graphs.
Mathematicians are often interested in constructing formula_2-regular Ramanujan graphs for every fixed formula_2. Current constructions of infinite families of such Ramanujan graphs are often algebraic.
It is still an open problem whether there are infinitely many formula_2-regular (non-bipartite) Ramanujan graphs for any formula_40. In particular, the problem is open for formula_43, the smallest case for which formula_44 is not a prime power and hence not covered by Morgenstern's construction.
Ramanujan graphs as expander graphs.
The constant formula_45 in the definition of Ramanujan graphs is the best possible constant for each formula_2 and for large graphs: in other words, for every formula_2 and formula_48, there exists formula_3 such that all formula_2-regular graphs formula_1 with at least formula_3 vertices satisfy formula_53. (See below for more precise statements and proof sketches.) On the other hand, Friedman showed that for every formula_2 and formula_48 and for sufficiently large formula_3, a random formula_2-regular formula_3-vertex graph formula_1 satisfies formula_60 with high probability. This means that Ramanujan graphs are essentially the best possible expander graphs. 
Due to achieving the tight bound on formula_61, 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.
Extremality of Ramanujan graphs.
If formula_1 is a formula_2-regular graph with diameter formula_64, a theorem due to Noga Alon states
Whenever formula_1 is formula_2-regular and connected on at least three vertices, formula_68, and therefore formula_69. Let formula_70 be the set of all connected formula_2-regular graphs formula_1 with at least formula_3 vertices. Because the minimum diameter of graphs in formula_70 approaches infinity for fixed formula_2 and increasing formula_3, this theorem implies an earlier theorem of Alon and Boppana which states
A slightly stronger bound is
where formula_79. The outline of the proof is the following. Take formula_80. Let formula_81 be the complete formula_82-ary tree of height formula_83 (each internal vertex has formula_44 children), and let formula_85 be its adjacency matrix. We want to prove that formula_86, where formula_87. Define a function formula_88 by formula_89, where formula_90 is the distance from formula_91 to the root of formula_81. One can verify that formula_93 and that formula_94 is indeed the largest eigenvalue of formula_85. Now let formula_96 and formula_97 be a pair of vertices at distance formula_64 in formula_1 and define
where formula_101 is a vertex in formula_81 which distance to the root is equal to the distance from formula_103 to formula_96 and the symmetric for formula_105. (One can think of this as "embedding" two disjoint copies of formula_106, with some vertices collapsed into one.) By choosing the value of positive reals formula_107 properly we get formula_108, formula_109 for formula_103 close to formula_96 and formula_112 for formula_103 close to formula_97. Then by the min-max theorem we getformula_115as desired. 