474 E. Groups and Graphs:::;
21~
12: llf(x) - f(v)ll^2 ,
(x,y)EEwhere m = lvl-^1 l:xEV v(x)f(x) EH is the mean off.
Proof. The :first equality is routine to check. Let lE be the orthogonal
projection from L^2 (V, v) onto the subspace Cl of constant functions. It is
easy to see (lE Q9 1) (!) = m, where m E H is viewed as a constant function
in L^2 (V) Q9 H. It follows that
A1(X)(llflli2cv,v)®H - llmll~) = A1(X)llf - (JE@ l)(f)lli2cv)®H
:S ((!::. @IJt)f, J)L2(V)®1t=
21
~
12: llf(x) - f(v)11
2
.
(x,y)EE
DDefinition E.6. A sequence {Xn} of finite connected graphs is called a
sequence of expanders if lim IV(Xn) I = oo and inf Al (Xn) > 0.
Usually, a sequence of expanders is required to have uniformly bounded
degrees. By (discrete) probabilistic methods, it is relatively easy to show
that "most" d-regular graphs have "large" A1. However, the first explicit
construction of a sequence of expanders was given by Margulis using (rela-
tive) property (T). Recall that a group r has property (T) if the following
is true: If a unitary representation ( 7r, H) of r has a sequence en of unit
vectors such that lim lien - 7r(s)~nll = 0 for every s Er, then there exists a
unit vector e E H such that 7r(s)e = ~ for all s E r. Recall that 81(3, Z)
has property (T) (see Sections 6.4 and 12.1 for more information).
Theorem E. 7. Let r be a residually finite group with property (T) (e.g.,
r = 81(3, Z)) and S be a finite symmetric generating subset without the
unit. Let {r n} be a sequence of finite quotients of r such that the image Sn
of S in r n does not contain the unit. Then, the Cayley graphs X(r n, Sn)
form a sequence of expanders.
Proof. First note that the Cayley graphs Xn = X(r n, Sn) are all connected
and ISi-regular. Composing the left regular representation of r n with the
quotient homomorphism, we obtain a unitary representation (7rn,.€^2 (rn)) of
r. We observe that