In the mathematical field of
spectral graph theory, a Ramanujan graph is a
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 outdegr ...
whose
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 othe ...
is almost as large as possible (see
extremal graph theory
Extremal graph theory is a branch of combinatorics, itself an area of mathematics, that lies at the intersection of extremal combinatorics and graph theory. In essence, extremal graph theory studies how global properties of a graph influence local ...
). Such graphs are excellent
spectral expanders. A
Murty's survey papernotes, Ramanujan graphs "fuse diverse branches of pure mathematics, namely,
number theory
Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic function, integer-valued functions. German mathematician Carl Friedrich Gauss (1777â ...
,
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 studies modules over these abstract algebraic structures. In essen ...
, and
algebraic geometry
Algebraic geometry is a branch of mathematics, classically studying zeros of multivariate polynomials. Modern algebraic geometry is based on the use of abstract algebraic techniques, mainly from commutative algebra, for solving geometrical ...
".
These graphs are indirectly named after
Srinivasa Ramanujan
Srinivasa Ramanujan (; born Srinivasa Ramanujan Aiyangar, ; 22 December 188726 April 1920) was an Indian mathematician. Though he had almost no formal training in pure mathematics, he made substantial contributions to mathematical analysis ...
; their name comes from the
Ramanujan–Petersson conjecture In mathematics, the Ramanujan conjecture, due to , states that Ramanujan's tau function given by the Fourier coefficients of the cusp form of weight
:\Delta(z)= \sum_\tau(n)q^n=q\prod_\left (1-q^n \right)^ = q-24q^2+252q^3- 1472q^4 + 4830q^5-\ ...
, 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
In linear algebra, an eigenvector () or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denoted b ...
of the
adjacency matrix
In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.
In the special case of a finite simp ...
of
(or the
spectrum
A spectrum (plural ''spectra'' or ''spectrums'') is a condition that is not limited to a specific set of values but can vary, without gaps, across a continuum. The word was first used scientifically in optics to describe the rainbow of colors i ...
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
is a Japanese mathematician and author of many books and essays on mathematics and mathematical sciences. He is professor emeritus of both Meiji University and Tohoku University. He is also distinguished professor of emeritus at Meiji in recogni ...
, a regular graph is Ramanujan if and only if its
Ihara zeta function In mathematics, 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 walks to the spectrum of the adjacency matrix. The Ihara zeta function was first ...
satisfies an analog of the
Riemann hypothesis
In mathematics, the Riemann hypothesis is the conjecture that the Riemann zeta function has its zeros only at the negative even integers and complex numbers with real part . Many consider it to be the most important unsolved problem in ...
.
Examples and constructions
Explicit examples
* The
complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is ...
has spectrum
, and thus
and the graph is a Ramanujan graph for every
. The
complete bipartite graph
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17.
Graph theory i ...
has spectrum
and hence is a bipartite Ramanujan graph for every
.
* The
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 n ...
has spectrum
, so it is a 3-regular Ramanujan graph. The
icosahedral graph
In geometry, a regular icosahedron ( or ) is a convex polyhedron with 20 faces, 30 edges and 12 vertices. It is one of the five Platonic solids, and the one with the most faces.
It has five equilateral triangular faces meeting at each vertex. It ...
is a 5-regular Ramanujan graph.
* A
Paley graph
In mathematics, Paley graphs are dense undirected graphs constructed from the members of a suitable finite field by connecting pairs of elements that differ by a quadratic residue. The Paley graphs form an infinite family of conference graphs, ...
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
In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem (named after Arthur Cay ...
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
Sarnak and independently
Margulis showed how to construct an infinite family of
-regular Ramanujan graphs, whenever
is a
prime number
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
and
. Both proofs use the
Ramanujan conjecture, which led to the name of Ramanujan graphs. Besides being Ramanujan graphs, these constructions satisfies some other properties, for example, their
girth is
where
is the number of nodes.
Let us sketch the Lubotzky-Phillips-Sarnak construction. Let
be a prime not equal to
. By
Jacobi's four-square theorem
Jacobi's four-square theorem gives a formula for the number of ways that a given positive integer ''n'' can be represented as the sum of four squares.
History
The theorem was proved in 1834 by Carl Gustav Jakob Jacobi.
Theorem
Two representati ...
, there are
solutions to the equation
where
is odd and
are even. To each such solution associate the
matrix
If
is a quadratic residue modulo
let
be the Cayley graph of
with these
generators, and otherwise, let
be the Cayley graph of
with the same generators. Then
is a
-regular graph on
or
vertices depending on whether or not
is a quadratic residue modulo
. It is proved that
is a Ramanujan graph.
Morgenstern
later extended the construction of Lubotzky, Phillips and Sarnak. His extended construction holds whenever
is a
prime power
In mathematics, a prime power is a positive integer which is a positive integer power of a single prime number.
For example: , and are prime powers, while
, and are not.
The sequence of prime powers begins:
2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17 ...
.
Arnold Pizer proved that the
supersingular isogeny graph
In mathematics, the supersingular isogeny graphs are a class of expander graphs that arise in computational number theory and have been applied in elliptic-curve cryptography. Their vertices represent supersingular elliptic curves over finite field ...
s are Ramanujan, although they tend to have lower girth than the graphs of Lubotzky, Phillips, and Sarnak. Like the graphs of Lubotzky, Phillips, and Sarnak, the degrees of these graphs are always a prime number plus one.
Probabilistic examples
Adam Marcus,
Daniel Spielman
Daniel Alan Spielman (born March 1970 in Philadelphia, Pennsylvania) has been a professor of applied mathematics and computer science at Yale University since 2006. As of 2018, he is the Sterling Professor of Computer Science at Yale. He is a ...
and
Nikhil Srivastava
Nikhil Srivastava is an associate professor of Mathematics at University of California, Berkeley. In July 2014, he was named a recipient of the PĂłlya Prize with Adam Marcus and Daniel Spielman.
Early life and education
Nikhil Srivastava was bo ...
proved the existence of infinitely many
-regular ''bipartite'' Ramanujan graphs for any
. Later
they proved that there exist bipartite Ramanujan graphs of every degree and every number of vertices. Michael B. Cohen
showed how to construct these graphs in polynomial time.
The initial work followed an approach of Bilu and
Linial. They considered an operation called a 2-lift that takes a
-regular graph
with
vertices and a sign on each edge, and produces a new
-regular graph
on
vertices. Bilu & Linial conjectured that there always exists a signing so that every new eigenvalue of
has magnitude at most
. This conjecture guarantees the existence of Ramanujan graphs with degree
and
vertices for any
—simply start with the complete graph
, and iteratively take 2-lifts that retain the Ramanujan property.
Using the method of interlacing polynomials, Marcus, Spielman, and Srivastava
proved Bilu & Linial's conjecture holds when
is already a bipartite Ramanujan graph, which is enough to conclude the existence result. The sequel
proved the stronger statement that a sum of
random bipartite matchings is Ramanujan with non-vanishing probability.
It is still an open problem whether there are infinitely many
-regular (non-bipartite) Ramanujan graphs for any
. In particular, the problem is open for
, the smallest case for which
is not a prime power and hence not covered by Morgenstern's construction.
Ramanujan graphs as expander graphs
The constant
in the definition of Ramanujan graphs is asymptotically sharp. More precisely, the
Alon-Boppana bound states that for every
and
, there exists
such that all
-regular graphs
with at least
vertices satisfy
. This means that Ramanujan graphs are essentially the best possible
expander graph
In graph theory, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion. Expander constructions have spawned research in pure and applied mathematics, with several applica ...
s.
Due to achieving the tight bound on
, the
expander mixing lemma The expander mixing lemma intuitively states that the edges of certain d-regular graphs are evenly distributed throughout the graph. In particular, the number of edges between two vertex subsets S and T is always close to the expected number of edge ...
gives excellent bounds on the uniformity of the distribution of the edges in Ramanujan graphs, and any
random walk
In mathematics, a random walk is a random process that describes a path that consists of a succession of random steps on some mathematical space.
An elementary example of a random walk is the random walk on the integer number line \mathbb Z ...
s on the graphs has a logarithmic
mixing time (in terms of the number of vertices): in other words, the random walk converges to the (uniform)
stationary distribution Stationary distribution may refer to:
* A special distribution for a Markov chain such that if the chain starts with its stationary distribution, the marginal distribution of all states at any time will always be the stationary distribution. Assum ...
very quickly. Therefore, the diameter of Ramanujan graphs are also bounded logarithmically in terms of the number of vertices.
Random graphs
Confirming a conjecture of
Alon Alon or ALON may refer to:
* Alon (name), an Israeli given name and surname
* Alon, Mateh Binyamin, an Israeli settlement in the West Bank
* Alon Inc, an American airplane builder, known for the Alon A-4
* Alon USA, an American energy company
* Alu ...
, Friedman showed that many families of random graphs are ''weakly-Ramanujan''. This means that for every
and
and for sufficiently large
, a random
-regular
-vertex graph
satisfies
with high probability. While this result shows that random graphs are close to being Ramanujan, it cannot be used to prove the existence of Ramanujan graphs. It is conjectured, though, that random graphs are Ramanujan with substantial probability (roughly 52%). In addition to direct numerical evidence, there is some theoretical support for this conjecture: the spectral gap of a
-regular graph seems to behave according to a
Tracy-Widom distribution from random matrix theory, which would predict the same asymptotic.
Applications of Ramanujan graphs
Expander graphs have many
applications
Application may refer to:
Mathematics and computing
* Application software, computer software designed to help the user to perform specific tasks
** Application layer, an abstraction layer that specifies protocols and interface methods used in a c ...
to computer science, number theory, and group theory, see e.
Lubotzky's surveyon applications to pure and applied math an
Hoory, Linial, and Wigderson's surveywhich focuses on computer science.. Ramanujan graphs are in some sense the best expanders, and so they are especially useful in applications where expanders are needed. Importantly, the Lubotzky, Phillips, and Sarnak graphs can be traversed extremely quickly in practice, so they are practical for applications.
Some example applications include
* In an application to fast solvers for Laplacian linear systems, Lee, Peng, and Spielman relied on the existence of bipartite Ramanujan graphs of every degree in order to quickly approximate the complete graph.
*Lubetzky and
Peres proved that the simple random walk exhibits
cutoff phenomenon on all Ramanujan graphs. This means that the random walk undergoes a phase transition from being completely unmixed to completely mixed in the total variation norm. This result strongly relies on the graph being Ramanujan, not just an expander—some good expanders are known to not exhibit cutoff.
* Ramanujan graphs of Pizer have been proposed as the basis for
post-quantum elliptic-curve cryptography
Elliptic-curve cryptography (ECC) is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. ECC allows smaller keys compared to non-EC cryptography (based on plain Galois fields) to provide eq ...
.
* Ramanujan graphs can be used to construct
expander codes, which are good
error correcting codes
In computing, telecommunication, information theory, and coding theory, an error correction code, sometimes error correcting code, (ECC) is used for controlling errors in data over unreliable or noisy communication channels. The central idea is ...
.
See also
*
Expander graph
In graph theory, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion. Expander constructions have spawned research in pure and applied mathematics, with several applica ...
*
Alon-Boppana bound
*
Expander mixing lemma The expander mixing lemma intuitively states that the edges of certain d-regular graphs are evenly distributed throughout the graph. In particular, the number of edges between two vertex subsets S and T is always close to the expected number of edge ...
*
Spectral graph theory
References
Further reading
*
* {{cite conference
, last = Sunada , first = Toshikazu
, editor1-last = Shiohama , editor1-first = Katsuhiro
, editor2-last = Sakai , editor2-first = Takashi
, editor3-last = Sunada , editor3-first = Toshikazu
, contribution = {{mvar, L-functions in geometry and some applications
, doi = 10.1007/BFb0075662
, isbn = 978-3-540-16770-9
, location = Berlin
, mr = 859591
, pages = 266–284
, publisher = Springer
, series = Lecture Notes in Mathematics
, title = Curvature and Topology of Riemannian Manifolds: Proceedings of the 17th International Taniguchi Symposium held in Katata, Japan, August 26–31, 1985
, volume = 1201
, year = 1986
External links
Survey paper by M. Ram MurtySurvey paper by Alexander LubotzkySurvey paper by Hoory, Linial, and Wigderson
Graph families
Algebraic graph theory
Spectral theory
Regular graphs
Srinivasa Ramanujan