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 . Define. A connected -regular graph is a Ramanujan graph if. Many sources uses an alternative definition to define Ramanujan graphs. In other words, we allow in addition to the "small" eigenvalues. Since 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 has spectrum, and thus and the graph is a Ramanujan graph for every. The complete bipartite graph has spectrum and hence is a bipartite Ramanujan graph for every. The Petersen graph has spectrum, so it is a 3-regular Ramanujan graph. The icosahedral graph is a 5-regular Ramanujan graph. A Paley graph of order is -regular with all other eigenvalues being, making Paley graphs an infinite family of Ramanujan graphs. Mathematicians are often interested in constructing -regular Ramanujan graphs for every fixed. Current constructions of infinite families of such Ramanujan graphs are often algebraic.
Lubotzky, Phillips and Sarnak show how to construct an infinite family of -regular Ramanujan graphs, whenever is a prime number and. Their proof uses the Ramanujan conjecture, which led to the name of Ramanujan graphs. Besides being Ramanujan graphs, their construction satisfies some other properties, for example, their girth is where is the number of nodes.
Morgenstern extended the construction of Lubotzky, Phillips and Sarnak. His extended construction holds whenever is a prime power.
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. Like the graphs of Lubotzky, Phillips, and Sarnak, the degrees of these graphs are always a prime number plus one. These graphs have been proposed as the basis for post-quantumelliptic-curve cryptography.
Adam Marcus, Daniel Spielman and Nikhil Srivastava proved the existence of infinitely many -regular bipartite Ramanujan graphs for any. Later they proved that there exist bipartite Ramanujan graphs of every degree and every number of vertices. Michael B. Cohen showed how to construct these graphs in polynomial time.
It is still an open problem whether there are infinitely many -regular Ramanujan graphs for any. In particular, the problem is open for, the smallest case for which is not a prime power and hence not covered by Morgenstern's construction.
The constant in the definition of Ramanujan graphs is the best possible constant for each and for large graphs: in other words, for every and, there exists such that all -regular graphs with at least vertices satisfy. On the other hand, Friedman showed that for every and and for sufficiently large, a random -regular -vertex graph satisfies with high probability. This means that Ramanujan graphs are essentially the best possible expander graphs. Due to achieving the tight bound on, 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 other words, the random walk converges to the 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 is a -regular graph with diameter, a theorem due to Noga Alon 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, this theorem implies an earlier theorem of Alon and Boppana which states A slightly stronger bound is where. The outline of the proof is the following. Take. Let be the complete -ary tree of height , and let be its adjacency matrix. We want to prove that, where. Define a function by, where is the distance from to the root of. One can verify that and that is indeed the largest eigenvalue of. Now let and be a pair of vertices at distance in and define where is a vertex in which distance to the root is equal to the distance from to and the symmetric for. By choosing the value of positive reals properly we get, for close to and for close to. Then by the min-max theorem we getas desired.
