Cryptography Reference
In-Depth Information
1
2
3
4
5
6
Figure 25.1 A 3-regular graph.
Let
X
be a
k
-regular graph. Then
k
−
λ
1
(
X
)
2
#
δ
e
(
A
)
≥
#
A
(25.5)
when #
A
#
X/
2 (see Theorem 1.3.1 of Davidoff, Sarnak and Valette [
153
] or Section 4
of Murty [
400
]
9
). Hence, #
δ
v
(
A
)
≤
(
2
−
λ
1
(
X
)
/
(2
k
))#
A
and so Ramanujan graphs are
expander graphs. Indeed, small values for
λ
1
(
X
) give large expansion factors. We refer
to [
153
,
400
] for further details and references.
≥
Exercise 25.3.15
Consider the 3-regular graph
X
in Figure
25.1
. Determine the eigenvalues
of
X
. Is this graph Ramanujan? Determine
δ
v
(
{
1
}
),
δ
v
(
{
1
,
2
}
) and
δ
v
(
{
1
,
3
}
). Verify that
#
δ
v
(
A
)
≥
#
A
for all subsets
A
of vertices of
X
such that #
A
≤
3 and so
X
is an expander.
Exercise 25.3.16
For every
c>
0 find an integer
n
∈ N
, a graph
X
with
n
vertices, and a
subset
A
of
X
such that #
A
≤
n/
2but#
δ
v
(
A
)
<c
#
A
. (Such a graph is very far from being
an expander.)
Consider the ordinary iso
geny gr
aph of elliptic curves over
F
q
with End(
E
)
=
O
K
,the
(
t
2
ring of integers in
K
4
q
). This was shown in the previous section to be a Cayley
graph for the ideal class group Cl(
= Q
−
O
K
). Jao, Miller and Venkatesan [
278
] show, assuming
a generalisation of the Riemann hypothesis, that the ordinary isogeny graph is an expander
graph (indeed, it is “nearly Ramanujan”, i.e.
λ
1
(
X
)
≤
O
(
k
β
)forsome0
<β<
1).
25.3.3 Supersingular isogeny graph
For the supersingular isogeny graph we work over
F
p
. The graph is finite. Indeed, The-
orem
9.11.11
implies
p/
12
−
1
<
#
X
E,
F
p
,S
<p/
12
+
2. Note that it suffices to co
ns
ider
elliptic curves defined over
F
p
2
(although the isogenies between them are over
F
p
in
general).
In contrast to the ordinary case, the supersingular graph is always connected using
isogenies of any fixed degree. A proof of this result, attributed to Serre, is given in Section 2.4
of Mestre [
377
].
9
Note that the proof on page 16 of [
400
]isfor
δ
e
(
A
), not
δ
v
(
A
) as stated.
