A Ramanujan graph, named after Srinivasa Ramanujan

Srinivasa Ramanujan

Srīnivāsa Aiyangār Rāmānujan FRS, better known as Srinivasa Iyengar Ramanujan was a Indian mathematician and autodidact who, with almost no formal training in pure mathematics, made extraordinary contributions to mathematical analysis, number theory, infinite series and continued fractions...

, is a regular

Regular graph

In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each vertex are equal to each other...

 graph

Graph (mathematics)

In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...

 whose spectral gap

Spectral gap

In mathematics, the spectral gap is the difference between the moduli of the two largest eigenvalues of a matrix or operator; alternately, it is sometimes taken as the smallest non-zero eigenvalue. Various theorems relate this difference to other properties of the system.See:* Expander graph *...

 is almost as large as possible (see extremal graph theory

Extremal graph theory

Extremal graph theory is a branch of the mathematical field of graph theory. Extremal graph theory studies extremal graphs which satisfy a certain property. Extremality can be taken with respect to different graph invariants, such as order, size or girth...

). Such graphs are excellent spectral expanders

Expander graph

In combinatorics, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion as described below...

.

Examples of Ramanujan graphs include the clique

Clique (graph theory)

In the mathematical area of graph theory, a clique in an undirected graph is a subset of its vertices such that every two vertices in the subset are connected by an edge. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs...

, the biclique , and the Petersen graph

Petersen graph

In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named for Julius Petersen, who in 1898 constructed it...

. As Murty's survey paper notes, Ramanujan graphs "fuse diverse branches of pure mathematics, namely, number theory

Number theory

Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...

, representation theory

Representation theory

Representation theory is a branch of mathematics that studies abstract algebraic structures by representing their elements as linear transformations of vector spaces, and studiesmodules over these abstract algebraic structures...

, and algebraic geometry

Algebraic geometry

Algebraic geometry is a branch of mathematics which combines techniques of abstract algebra, especially commutative algebra, with the language and the problems of geometry. It occupies a central place in modern mathematics and has multiple conceptual connections with such diverse fields as complex...

".

Definition

Let be a connected -regular graph with vertices, and let be the eigenvalues of the adjacency matrix

Adjacency matrix

In mathematics and computer science, an adjacency matrix is a means of representing which vertices of a graph are adjacent to which other vertices...

 of (see Spectral graph theory

Spectral graph theory

In mathematics, spectral graph theory is the study of properties of a graph in relationship to the characteristic polynomial, eigenvalues, and eigenvectors of matrices associated to the graph, such as its adjacency matrix or Laplacian matrix....

). Because is connected and -regular, its eigenvalues satisfy . Whenever there exists with , define

A -regular graph is a Ramanujan graph if is defined and .

A Ramanujan graph is characterized as a regular graph whose Ihara zeta function

Ihara zeta function

The Ihara zeta-function is a zeta function associated with a finite graph. It closely resembles the Selberg zeta-function, and is used to relate closed paths to the spectrum of the adjacency matrix. The Ihara zeta-function was first defined by Yasutaka Ihara in the 1960s in the context of discrete...

 satisfies an analogue of the Riemann Hypothesis

Riemann hypothesis

In mathematics, the Riemann hypothesis, proposed by , is a conjecture about the location of the zeros of the Riemann zeta function which states that all non-trivial zeros have real part 1/2...

.

Extremality of Ramanujan graphs

For a fixed and large , the -regular, -vertex Ramanujan graphs minimize . If is a -regular graph with diameter , a theorem due to Nilli (pseudonym of Noga Alon

Noga Alon

Noga Alon is an Israeli mathematician noted for his contributions to combinatorics and theoretical computer science, having authored hundreds of papers.- Academic background :...

) states

Whenever is -regular and connected on at least three vertices, , and therefore . Let be the set of all connected -regular graphs with at least vertices. Because the minimum diameter of graphs in approaches infinity for fixed and increasing , Nilli's theorem implies an earlier theorem of Alon

Noga Alon

Noga Alon is an Israeli mathematician noted for his contributions to combinatorics and theoretical computer science, having authored hundreds of papers.- Academic background :...

 and Boppana which states

Constructions

Constructions of Ramanujan graphs are often algebraic. Lubotzky

Alexander Lubotzky

Professor Alexander Lubotzky is an Israeli academic and former politician. A former head of the Mathematics Institute at the Hebrew University of Jerusalem, he served as a member of the Knesset for The Third Way party between 1996 and 1999.-Education:...

, Phillips and Sarnak

Peter Sarnak

Peter Clive Sarnak is a South African-born mathematician. He has been Eugene Higgins Professor of Mathematics at Princeton University since 2002, succeeding Andrew Wiles, and is an editor of the Annals of Mathematics...

 show how to construct an infinite family of p +1-regular Ramanujan graphs, whenever p ≡ 1 (mod 4) is a prime

Prime number

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...

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