Ramanujan Graphs
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.
Ramanujan Graphs

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 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.[1] 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.[2]

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.[3]

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[1] 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[4] 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.[5] 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-quantum elliptic-curve cryptography.[6]
  • Adam Marcus, Daniel Spielman and Nikhil Srivastava[7] proved the existence of infinitely many -regular bipartite Ramanujan graphs for any . Later[8] they proved that there exist bipartite Ramanujan graphs of every degree and every number of vertices. Michael B. Cohen[9] 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[10] 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.

Extremality of Ramanujan graphs

If is a -regular graph with diameter , a theorem due to Noga Alon[11] 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[12] 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

as desired.

See also

References

  1. ^ a b Alexander Lubotzky; Ralph Phillips; Peter Sarnak (1988). "Ramanujan graphs". Combinatorica. 8 (3): 261-277. doi:10.1007/BF02126799. S2CID 206812625.
  2. ^ Terras, Audrey (2011), Zeta functions of graphs: A stroll through the garden, Cambridge Studies in Advanced Mathematics, 128, Cambridge University Press, ISBN 978-0-521-11367-0, MR 2768284
  3. ^ Weisstein, Eric W. "Icosahedral Graph". mathworld.wolfram.com. Retrieved .
  4. ^ Moshe Morgenstern (1994). "Existence and Explicit Constructions of q+1 Regular Ramanujan Graphs for Every Prime Power q". Journal of Combinatorial Theory, Series B. 62: 44-62. doi:10.1006/jctb.1994.1054.
  5. ^ Pizer, Arnold K. (1990), "Ramanujan graphs and Hecke operators", Bulletin of the American Mathematical Society, New Series, 23 (1): 127-137, doi:10.1090/S0273-0979-1990-15918-X, MR 1027904
  6. ^ Eisenträger, Kirsten; Hallgren, Sean; Lauter, Kristin; Morrison, Travis; Petit, Christophe (2018), "Supersingular isogeny graphs and endomorphism rings: Reductions and solutions" (PDF), in Nielsen, Jesper Buus; Rijmen, Vincent (eds.), Advances in Cryptology - EUROCRYPT 2018: 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29 - May 3, 2018, Proceedings, Part III (PDF), Lecture Notes in Computer Science, 10822, Cham: Springer, pp. 329-368, doi:10.1007/978-3-319-78372-7_11, MR 3794837
  7. ^ Adam Marcus; Daniel Spielman; Nikhil Srivastava (2013). Interlacing families I: Bipartite Ramanujan graphs of all degrees. Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium.
  8. ^ Adam Marcus; Daniel Spielman; Nikhil Srivastava (2015). Interlacing families IV: Bipartite Ramanujan graphs of all sizes. Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium.
  9. ^ Michael B. Cohen (2016). Ramanujan Graphs in Polynomial Time. Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium. arXiv:1604.03544. doi:10.1109/FOCS.2016.37.
  10. ^ Friedman, Joel (2003). "Relative expanders or weakly relatively Ramanujan graphs". Duke Math. J. 118 (1): 19-35. doi:10.1215/S0012-7094-03-11812-8. MR 1978881.
  11. ^ Nilli, A. (1991), "On the second eigenvalue of a graph", Discrete Mathematics, 91 (2): 207-210, doi:10.1016/0012-365X(91)90112-F, MR 1124768.
  12. ^ Alon, N. (1986). "Eigenvalues and expanders". Combinatorica. 6 (2): 83-96. doi:10.1007/BF02579166. MR 0875835. S2CID 41083612.

Further reading

External links


  This article uses material from the Wikipedia page available here. It is released under the Creative Commons Attribution-Share-Alike License 3.0.

Ramanujan_graphs
 



 



 
Music Scenes