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.
