Ramanujan graph

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