Ramanujan graph

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. 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 K n , n {displaystyle K_{n,n}} , 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 G {displaystyle G} be a connected d {displaystyle d} -regular graph with n {displaystyle n} vertices, and let λ 0 ≥ λ 1 ≥ ⋯ ≥ λ n − 1 {displaystyle lambda _{0}geq lambda _{1}geq cdots geq lambda _{n-1}} be the eigenvalues of the adjacency matrix of G {displaystyle G} . Because G {displaystyle G} is connected and d {displaystyle d} -regular, its eigenvalues satisfy d = λ 0 > λ 1 {displaystyle d=lambda _{0}>lambda _{1}} ≥ ⋯ ≥ λ n − 1 ≥ − d {displaystyle geq cdots geq lambda _{n-1}geq -d} . Whenever there exists λ i {displaystyle lambda _{i}} with | λ i | < d {displaystyle |lambda _{i}|<d} , define A d {displaystyle d} -regular graph G {displaystyle G} is a Ramanujan graph if λ ( G ) ≤ 2 d − 1 {displaystyle lambda (G)leq 2{sqrt {d-1}}} . A Ramanujan graph is characterized as a regular graph whose Ihara zeta function satisfies an analogue of the Riemann Hypothesis. For a fixed d {displaystyle d} and large n {displaystyle n} , the d {displaystyle d} -regular, n {displaystyle n} -vertex Ramanujan graphs nearly minimize λ ( G ) {displaystyle lambda (G)} . If G {displaystyle G} is a d {displaystyle d} -regular graph with diameter m {displaystyle m} , a theorem due to Noga Alon states Whenever G {displaystyle G} is d {displaystyle d} -regular and connected on at least three vertices, | λ 1 | < d {displaystyle |lambda _{1}|<d} , and therefore λ ( G ) ≥ λ 1 {displaystyle lambda (G)geq lambda _{1}} . Let G n d {displaystyle {mathcal {G}}_{n}^{d}} be the set of all connected d {displaystyle d} -regular graphs G {displaystyle G} with at least n {displaystyle n} vertices. Because the minimum diameter of graphs in G n d {displaystyle {mathcal {G}}_{n}^{d}} approaches infinity for fixed d {displaystyle d} and increasing n {displaystyle n} , this theorem implies an earlier theorem of Alon and Boppana which states