Cryptography Reference
In-Depth Information
25.3.2 Expander graphs and Ramanujan graphs
Let
X
be a finite (directed) graph on vertices labelled
{
1
,...,n
}
.The
adjacency matrix
of
X
is the
n
n
integer matrix
A
with
A
i,j
being the number of edges from vertex
i
to vertex
j
.The
eigenvalues of a finite graph
X
are defined to be the eigenvalues of its adjacency
matrix
A
. For the rest of this section we assume that all graphs are un-directed. Since the
adjacency matrix of an un-directed graph is real and symmetric, the eigenvalues are real.
×
Lemma 25.3.11
Let X be a k-regular graph. Then k is an eigenvalue, and all eigenvalues
λ are such that
|
λ
|≤
k.
Proof
The first statement follows since (1
,
1
,...,
1) is an eigenvector with eigenvalue
k
.The
second statement is also easy (see Proposition 1.1.2 of Davidoff, Sarnak and Valette [
153
]
or Theorem 1 of Murty [
400
]).
Let
X
be a
k
-regular graph. We denote by
λ
(
X
) the maximum of the absolute values
of all the eigenvalues that are not equal to
k
. Alon and Boppana showed that the lim inf
of
λ
(
X
)
over
any family of
k
-regular graphs (as the number of vertices goes to
±
∞
)isat
least 2
√
k
1 (see Theorem 1.3.1 of [
153
], Theorem
3.2 of
[
431
] or Theorem 10 of [
400
]).
The graph
X
is said to be
Ramanujan
if
λ
(
X
)
−
2
√
k
≤
−
1. Define
λ
1
(
X
) to be the largest
eigenvalue that is strictly less than
k
.
Let
G
be a finite group and
S
a subset of
G
such that
g
∈
S
implies
g
−
1
∈
S
(we also
allow
S
to be a multi-set). The
Cayley graph
of
G
is the graph
X
with vertex set
G
and an
edge between
g
and
gs
for all
g
∈
∈
S
.Murty[
400
] surveys criteria for when
a Cayley graph is a Ramanujan graph. If certain character sums are small then
X
may be a
Ramanujan graph; see Section 2 of [
400
].
G
and all
s
Definition 25.3.12
Let
X
be a graph and
A
a subset of vertices of
X
.The
vertex boundary
of
A
in
X
is
={
∈
−
}
δ
v
(
A
)
v
X
A
: there is an edge between
v
and a vertex in
A
.
Let
E
X
be the set of edges (
x,y
)in
X
.The
edge boundary
of
A
in
X
is
δ
e
(
A
)
={
(
x,y
)
∈
E
X
:
x
∈
A
and
y
∈
X
−
A
}
.
Let
c>
0 be real. A
k
-regular graph
X
with #
X
vertices is a
c
-expander
if, for all subsets
A
⊆
X
such that #
A
≤
#
X/
2
#
δ
v
(
A
)
≥
c
#
A.
Exercise 25.3.13
Show that
δ
v
(
A
)
≤
δ
e
(
A
)
≤
kδ
v
(
A
).
Exercise 25.3.14
Let
X
be a
k
-regular graph with
n
vertices that is a
c
-expander. Show
that if
n
is even then 0
≤
c
≤
1 and if
n
is odd then 0
≤
c
≤
(
n
+
1)
/
(
n
−
1).
Expander graphs have a number of theoretical applications; one important property is
that random walks on expander graphs reach the uniform distribution quickly.
