In the mathematical field of 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[1] 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

edit

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.[2] 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. If   is a Ramanujan graph, then   is a bipartite Ramanujan graph, so the existence of Ramanujan graphs is stronger.

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]

Examples and constructions

edit

Explicit examples

edit
  • 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.[4]
  • A Paley graph of order   is  -regular with all other eigenvalues being  , making Paley graphs an infinite family of Ramanujan graphs.
  • More generally, let   be a degree 2 or 3 polynomial over  . Let   be the image of   as a multiset, and suppose  . Then the Cayley graph for   with generators from   is a Ramanujan graph.

Mathematicians are often interested in constructing infinite families of  -regular Ramanujan graphs for every fixed  . Such families are useful in applications.

Algebraic constructions

edit

Several explicit constructions of Ramanujan graphs arise as Cayley graphs and are algebraic in nature. 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  -regular Ramanujan graphs, whenever   is a prime number and  . Both proofs use the Ramanujan conjecture, which led to the name of Ramanujan graphs. Besides being Ramanujan graphs, these constructions satisfies some other properties, for example, their girth is   where   is the number of nodes.

Let us sketch the Lubotzky-Phillips-Sarnak construction. Let   be a prime not equal to  . By Jacobi's four-square theorem, there are   solutions to the equation   where   is odd and   are even. To each such solution associate the   matrix  If   is not a quadratic residue modulo   let   be the Cayley graph of   with these   generators, and otherwise, let   be the Cayley graph of   with the same generators. Then   is a  -regular graph on   or   vertices depending on whether or not   is a quadratic residue modulo  . It is proved that   is a Ramanujan graph.

Morgenstern[7] later 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.[8] Like the graphs of Lubotzky, Phillips, and Sarnak, the degrees of these graphs are always a prime number plus one.

Probabilistic examples

edit

Adam Marcus, Daniel Spielman and Nikhil Srivastava[9] proved the existence of infinitely many  -regular bipartite Ramanujan graphs for any  . 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. They considered an operation called a 2-lift that takes a  -regular graph   with   vertices and a sign on each edge, and produces a new  -regular graph   on   vertices. Bilu & Linial conjectured that there always exists a signing so that every new eigenvalue of   has magnitude at most  . This conjecture guarantees the existence of Ramanujan graphs with degree   and   vertices for any  —simply start with the complete graph  , 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.

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

edit

The constant   in the definition of Ramanujan graphs is asymptotically sharp. More precisely, the Alon-Boppana bound states that for every   and  , there exists   such that all  -regular graphs   with at least   vertices satisfy  . 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.

Random graphs

edit

Confirming a conjecture of Alon, Friedman[13] showed that many families of random graphs are weakly-Ramanujan. This means that for every   and   and for sufficiently large  , a random  -regular  -vertex graph   satisfies   with high probability. While this result shows that random graphs are close to being Ramanujan, it cannot be used to prove the existence of Ramanujan graphs. 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.

Applications of Ramanujan graphs

edit

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.. Ramanujan graphs are in some sense the best expanders, and so they are especially useful in applications where expanders are needed. Importantly, the Lubotzky, Phillips, and Sarnak graphs can be traversed extremely quickly in practice, so they are practical for applications.

Some example applications include

  • In an application to fast solvers for Laplacian linear systems, Lee, Peng, and Spielman[15] relied on the existence of bipartite Ramanujan graphs of every degree in order to quickly approximate the complete graph.
  • Lubetzky and Peres proved that the simple random walk exhibits cutoff phenomenon on all Ramanujan graphs.[16] This means that the random walk undergoes a phase transition from being completely unmixed to completely mixed in the total variation norm. This result strongly relies on the graph being Ramanujan, not just an expander—some good expanders are known to not exhibit cutoff.[17]
  • Ramanujan graphs of Pizer have been proposed as the basis for post-quantum elliptic-curve cryptography.[18]
  • Ramanujan graphs can be used to construct expander codes, which are good error correcting codes.

See also

edit

References

edit
  1. ^ Survey paper by M. Ram Murty
  2. ^ a b Alexander Lubotzky; Ralph Phillips; Peter Sarnak (1988). "Ramanujan graphs". Combinatorica. 8 (3): 261–277. doi:10.1007/BF02126799. S2CID 206812625.
  3. ^ Terras, Audrey (2011), Zeta functions of graphs: A stroll through the garden, Cambridge Studies in Advanced Mathematics, vol. 128, Cambridge University Press, ISBN 978-0-521-11367-0, MR 2768284
  4. ^ Weisstein, Eric W. "Icosahedral Graph". mathworld.wolfram.com. Retrieved 2019-11-29.
  5. ^ Li, Winnie (2020). "The Ramanujan conjecture and its applications". Philosophical Transactions of the Royal Society A. 378–2163 (2163). Bibcode:2020RSPTA.37880441W. doi:10.1098/rsta.2018.0441. PMC 6939229. PMID 31813366.
  6. ^ Margulis, G. A. (1988). "Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators". Probl. Peredachi Inf. 24–1: 51–60.
  7. ^ 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.
  8. ^ 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
  9. ^ a b Adam Marcus; Daniel Spielman; Nikhil Srivastava (2013). Interlacing families I: Bipartite Ramanujan graphs of all degrees (PDF). Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium.
  10. ^ a b Adam Marcus; Daniel Spielman; Nikhil Srivastava (2015). Interlacing families IV: Bipartite Ramanujan graphs of all sizes (PDF). Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium.
  11. ^ 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.
  12. ^ Hall, Chris; Puder, Doron; Sawin, William F. (2018). "Ramanujan coverings of graphs". Advances in Mathematics. 323: 367–410. arXiv:1506.02335. doi:10.1016/j.aim.2017.10.042.
  13. ^ Friedman, Joel (2003). "Relative expanders or weakly relatively Ramanujan graphs". Duke Mathematical Journal. 118 (1): 19–35. doi:10.1215/S0012-7094-03-11812-8. MR 1978881.
  14. ^ Miller, Steven J.; Novikoff, Tim; Sabelli, Anthony (2008). "The Distribution of the Largest Non-trivial Eigenvalues in Families of Random Regular Graphs". Experimental Mathematics. 17 (2): 231–244. arXiv:math/0611649. doi:10.1080/10586458.2008.10129029.
  15. ^ Lee, Yin Tat; Peng, Richard; Spielman, Daniel A. (2015-08-13). "Sparsified Cholesky Solvers for SDD linear systems". arXiv:1506.08204 [cs.DS].
  16. ^ Lubetzky, Eyal; Peres, Yuval (2016-07-01). "Cutoff on all Ramanujan graphs". Geometric and Functional Analysis. 26 (4): 1190–1216. arXiv:1507.04725. doi:10.1007/s00039-016-0382-7. ISSN 1420-8970. S2CID 13803649.
  17. ^ Lubetzky, Eyal; Sly, Allan (2011-01-01). "Explicit Expanders with Cutoff Phenomena". Electronic Journal of Probability. 16 (none). arXiv:1003.3515. doi:10.1214/EJP.v16-869. ISSN 1083-6489. S2CID 9121682.
  18. ^ 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, vol. 10822, Cham: Springer, pp. 329–368, doi:10.1007/978-3-319-78372-7_11, ISBN 978-3-319-78371-0, MR 3794837, S2CID 4850644

Further reading

edit
edit