Get Ramanujan Graphs essential facts below. View Videos or join the Ramanujan Graphs discussion. Add Ramanujan Graphs to your PopFlock.com topic list for future reference or share this resource on social media.
Let be a connected -regular graph with vertices, and let be the eigenvalues of the adjacency matrix of (or the spectrum 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 (whenever there exists with ) 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.
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 (non-bipartite) 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.
Ramanujan graphs as expander graphs
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 . (See below for more precise statements and proof sketches.) 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 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.
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 (each internal vertex has children), 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 . (One can think of this as "embedding" two disjoint copies of , with some vertices collapsed into one.) By choosing the value of positive reals properly we get , for close to and for close to . Then by the min-max theorem we get