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. 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. 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. Examples and constructions Explicit examples 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. Mathematicians are often interested in constructing infinite families of -regular Ramanujan graphs for every fixed . Such families are useful in applications. Algebraic constructions 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. Lubotzky, Phillips and