Ramanujan graph

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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


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 .

A Ramanujan graph is characterized as a regular graph whose Ihara zeta function satisfies an analogue of the Riemann Hypothesis.

Extremality of Ramanujan graphs[edit]

For a fixed and large , the -regular, -vertex Ramanujan graphs nearly minimize . If is a -regular graph with diameter , a theorem due to Nilli[2] 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 , Nilli's theorem implies an earlier theorem of Alon and Boppana which states

A slightly stronger bound is

where . The outline of Friedman's proof is the following. Take . Let be the -regular tree of height and let be its adjacency matrix. We want to prove that , for some depending only on . Define a function by , where is the distance from to the root of . Choosing a close to it can be proved that . Now let and be a pair of vertices at distance 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 properly we get , for close to and for close to . Then by the min-max theorem .


Constructions of Ramanujan graphs are often algebraic.

  • Lubotzky, Phillips and Sarnak[3] 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.
  • Adam Marcus, Daniel Spielman and Nikhil Srivastava[5] proved the existence of -regular bipartite Ramanujan graphs for any . Later[6] they proved that there exist bipartite Ramanujan graphs of every degree and every number of vertices. Michael B. Cohen[7] showed how to construct these graphs in polynomial time.


  1. ^ Audrey Terras, Zeta Functions of Graphs: A Stroll through the Garden, volume 128, Cambridge Studies in Advanced Mathematics, Cambridge University Press, (2010).
  2. ^ A Nilli, On the second eigenualue of a graph, Discrete Mathematics 91 (1991) pp. 207-210.
  3. ^ Alexander Lubotzky; Ralph Phillips; Peter Sarnak (1988). "Ramanujan graphs". Combinatorica. 8 (3): 261–277. doi:10.1007/BF02126799. 
  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. ^ 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. 
  6. ^ 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. 
  7. ^ Michael B. Cohen (2016). Ramanujan Graphs in Polynomial Time. Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium. doi:10.1109/FOCS.2016.37. 

External links[edit]