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 , 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 be a connected d -regular graph with n vertices, and let λ 0 ≥ λ 1 ≥ … ≥ λ n − 1 be the eigenvalues of the adjacency matrix of G . Because G is connected and d -regular, its eigenvalues satisfy d = λ 0 > λ 1 ≥ … ≥ λ n − 1 ≥ − d . Whenever there exists λ i with | λ i | < d , define
λ ( G ) = max | λ i | < d | λ i | . A d -regular graph G is a Ramanujan graph if λ ( G ) ≤ 2 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 and large n , the d -regular, n -vertex Ramanujan graphs nearly minimize λ ( G ) . If G is a d -regular graph with diameter m , a theorem due to Nilli states
λ 1 ≥ 2 d − 1 − 2 d − 1 − 1 ⌊ m / 2 ⌋ . Whenever G is d -regular and connected on at least three vertices, | λ 1 | < d , and therefore λ ( G ) ≥ λ 1 . Let G n d be the set of all connected d -regular graphs G with at least n vertices. Because the minimum diameter of graphs in G n d approaches infinity for fixed d and increasing n , Nilli's theorem implies an earlier theorem of Alon and Boppana which states
lim n → ∞ inf G ∈ G n d λ ( G ) ≥ 2 d − 1 . A slightly stronger bound is
λ 1 ≥ 2 d − 1 ⋅ ( 1 − c m 2 ) ,
where c ≈ 2 π 2 . The outline of Friedman's proof is the following. Take k = ⌊ m 2 ⌋ − 1 . Let T d , k be the d -regular tree of height k and let A T k be its adjacency matrix. We want to prove that λ ( G ) ≥ λ ( T d , k ) = 2 d − 1 cos θ , for some θ depending only on m . Define a function g : V ( T d , k ) → R by g ( x ) = ( d − 1 ) − δ / 2 ⋅ sin ( ( k + 1 − δ ) θ ) , where δ is the distance from x to the root of T d , k . Choosing a θ close to 2 π / m it can be proved that A t , k g = λ ( T d , k ) g . Now let s and t be a pair of vertices at distance m and define
f ( v ) = { c 1 g ( v s ) for v at distance ≤ k from s − c 2 g ( v t ) for v at distance ≤ k from t 0 otherwise ,
where v s is a vertex in T d , k which distance to the root is equal to the distance from v to s and the symmetric for v t . By choosing properly c 1 , c 2 we get f ⊥ 1 , ( A f ) v ≥ λ ( T d , k ) f v for v close to s and ( A f ) v ≤ λ ( T d , k ) f v for v close to t . Then by the min-max theorem λ ( G ) ≥ f A f T / | | f | | 2 ≥ λ ( T d , k ) .
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 is a prime number and p ≡ 1 ( mod 4 ) . 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 Ω ( log p ( n ) ) where n is the number of nodes.Morgenstern extended the construction of Lubotzky, Phillips and Sarnak. His extended construction holds whenever p is a prime power.Adam Marcus, Daniel Spielman and Nikhil Srivastava proved the existence of d -regular bipartite Ramanujan graphs for any d . Later they proved that there exist bipartite Ramanujan graphs of every degree and every number of vertices.