1550075568-C-Algebras_and_Finite-Dimensional_Approximations__Brown_

5.5. Coarse metric spaces 199

In particular, we have llf(x)ll < oo. On the other hand, if d(x,y) >
maxk~n sk, then
n
llf(x) - f(y)ll ~II EB(e~ -et) II= V2n.
k=l
This implies that f is a coarse embedding. 0

Recall from Appendix E that a sequence of expanders is a sequence {Xn}
of finite connected d-regular graphs (with d fixed) such that inf >..1(Xn) > 0
(the first nonzero eigenvalues of the Laplacians) and sup IXnl = oo. Here, we
identify the graph Xn with the finite metric space of its vertices. We can glue
the Xn's together to form a graph metric space X, with bounded geometry,
which contains the Xn's isometrically: choose a base point Xn E Xn, for
every n, and put an edge between Xn and Xn+i · We note that the degrees
of the vertices of X are at most d + 2 and every ball of radius S has at most
(d + 2)^8 elements. A map g from a graph metric space X into any metric
space Y is l-Lipschitz if dy(g(x), g(y)) :S 1 for every adjacent pair x and y
inX.

Proposition 5.5.9. Let X be a metric space with bounded geometry. As-
sume that there exists a sequence Xn of expanders with l-Lipschitz maps
9n : Xn --+ X such that

lim sup lg~l(Bs(x))I = 0

n-T<XlxEX IXnl

for every S > 0. Then X is not coarsely embeddable into a Hilbert space.
In particular, X does not have property A.

Proof. Let ).. 1 = inf >..1 (Xn) > 0. Suppose that there exists a coarse em-
bedding f of X into a Hilbert space H. We have

0 = )..~^112 sup JJf(x) - f(y)JI < oo.

dx(x,y)SI

Since f is a coarse embedding, there exists S > 0 such that llf(x) - f(y)JI :S
20 implies dx(x, y) < S. Now, let n be fixed. Applying Lemma E.5 to
fn = f o 9n: Xn--+ 1i, we have

~ L llfn(a) - fn(b)ll2 :S E ~ L Jlfn(a) ~ fn(b)ll2 :S 02.

IXnl a,bEXn I ( n)I (a,b)EE(Xn)^1

This implies the existence of a point a E Xn such that IXnl-^1 I:bEXn llfn(a)-
fn(b)ll2 :S 02. This further implies that the cardinality of the set {b E
Xn : Jlfn(a) - fn(b)ll :S 20} is greater than 3IXnl/4. It follows that
Jg~^1 (Bs(gn(a)))I ~ 3IXnl/4. Since n was arbitrary, this provides the de-
sired contradiction. D