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

Definition[edit]

Let G be a connected d-regular graph with n vertices, and let \lambda_0 \geq \lambda_1 \geq \ldots \geq \lambda_{n-1} be the eigenvalues of the adjacency matrix of G. Because G is connected and d-regular, its eigenvalues satisfy d = \lambda_0 > \lambda_1  \geq \ldots \geq \lambda_{n-1} \geq -d . Whenever there exists \lambda_i with |\lambda_i| < d, define[dubious ]

\lambda(G) = \max_{|\lambda_i| < d} |\lambda_i|.\,

A d-regular graph G is a Ramanujan graph if \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.

Extremality of Ramanujan graphs[edit]

For a fixed d and large n, the d-regular, n-vertex Ramanujan graphs nearly minimize \lambda(G). If G is a d-regular graph with diameter m, a theorem due to Nilli[2] states

\lambda_1 \geq 2\sqrt{d-1} - \frac{2\sqrt{d-1} - 1}{\lfloor m/2\rfloor}.

Whenever G is d-regular and connected on at least three vertices, |\lambda_1| < d, and therefore \lambda(G) \geq \lambda_1. Let \mathcal{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 \mathcal{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 \to \infty} \inf_{G \in \mathcal{G}_n^d} \lambda(G) \geq 2\sqrt{d-1}.

Constructions[edit]

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 ≡ 1 (mod 4) is a prime. Their proof uses the Ramanujan conjecture, which led to the name of Ramanujan graphs. Morgenstern extended the construction of Lubotzky, Phillips and Sarnak to all prime powers.

References[edit]

  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.
  • Guiliana Davidoff; Peter Sarnak; Alain Valette (2003). Elementary number theory, group theory and Ramanjuan graphs. LMS student texts 55. Cambridge University Press. ISBN 0-521-53143-8. OCLC 50253269. 
  • Alexander Lubotzky; Ralph Phillips; Peter Sarnak (1988). "Ramanujan graphs". Combinatorica 8 (3): 261–277. doi:10.1007/BF02126799. 
  • Moshe Morgenstern (1994). "Existence and Explicit Constructions of q+1 Regular Ramanujan Graphs for Every Prime Power q". J. Combinatorial Theory, Series B 62: 44–62. doi:10.1006/jctb.1994.1054. 
  • T. Sunada (1985). "L-functions in geometry and some applications". Lecture Notes in Math. Lecture Notes in Mathematics 1201: 266–284. doi:10.1007/BFb0075662. ISBN 978-3-540-16770-9. 

External links[edit]