In spectral graph theory, a Ramanujan graph, named after Srinivasa Ramanujan, is a regular graph whose spectral gap is almost as large as possible (see extremal graph theory). Such graphs are excellent spectral expanders.
Examples of Ramanujan graphs include the clique, the biclique , and the Petersen graph. As Murty's survey paper notes, Ramanujan graphs "fuse diverse branches of pure mathematics, namely, number theory, representation theory, and algebraic geometry". 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.
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 . Whenever there exists with , define
A -regular graph is a Ramanujan graph if is defined and .
Extremality of Ramanujan graphs
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 , Nilli's theorem implies an earlier theorem of Alon and Boppana which states
Constructions of Ramanujan graphs are often algebraic. Lubotzky, Phillips and Sarnak show how to construct an infinite family of p +1-regular Ramanujan graphs, whenever p ≡ 1 (mod 4) is a prime. Their proof uses the Ramanujan conjecture, which led to the name of Ramanujan graphs. Morgenstern extended the construction of Lubotzky, Phillips and Sarnak to all prime powers.
- Audrey Terras, Zeta Functions of Graphs: A Stroll through the Garden, volume 128, Cambridge Studies in Advanced Mathematics, Cambridge University Press, (2010).
- A Nilli, On the second eigenualue of a graph, Discrete Mathematics 91 (1991) pp. 207-210.
- Guiliana Davidoff; Peter Sarnak; Alain Valette (2003). Elementary number theory, group theory and Ramanjuan graphs. LMS student texts 55. Cambridge University Press. ISBN 0-521-53143-8. OCLC 50253269.
- Alexander Lubotzky; Ralph Phillips; Peter Sarnak (1988). "Ramanujan graphs". Combinatorica 8 (3): 261–277. doi:10.1007/BF02126799.
- Moshe Morgenstern (1994). "Existence and Explicit Constructions of q+1 Regular Ramanujan Graphs for Every Prime Power q". J. Combinatorial Theory, Series B 62: 44–62. doi:10.1006/jctb.1994.1054.
- T. Sunada (1985). "L-functions in geometry and some applications". Lecture Notes in Math. Lecture Notes in Mathematics 1201: 266–284. doi:10.1007/BFb0075662. ISBN 978-3-540-16770-9.