In the first and second lectures, I defined coarse embeddings and gave examples. Now I give more details.

**1. Examples of spaces not embeddable into Hilbert spaces **

Definition 1Let be a family of finite collected, -regular graphs, with increasing size. Say that is afamily of expandersif there exists such that edge expansion for all .

Such things exist. Pinsker obtained them using the probabilistic method in 1967. In 1973, Margulis gave explicit examples [M].

Theorem 2 (Margulis)Fix . Let be a finite symmetric generating set of . Then the family of Cayley graphs , , is a family of expanders.

Cheeger-Buser’s inequality relates edge-expansion to the first non-zero eigenvalue of the Laplacian, denoted here by (beware this is denoted by in James Lee’s course). This gives a spectral expansion criterion.

Proposition 3is a family of expanders iff there exists such that for all .

Linial, London and Rabinovich proved in 1994 that expanders do not embed coarsely in Hilbert space, [LLR].

Theorem 4Let equipped with a metric such that different are sufficiently far apart. Then has no coarse embedding into Hilbert space.

*Proof:* By contradiction. Let be such an embedding. One can use as a test function in the definition of . Indeed, choose a Hilbert basis, then each component of can be used, and sum up. Thus

so

For every , the number of pairs with is less than . For other pairs (the number of them is ), , so

If this holds for all , contradiction.

In 2000, Gromov sketched a construction of random groups containing a coarsely embedded family of expandres in their Cayley graphs. Such groups do not coarsely embed in Hilbert spaces.

Linial: with the new examples of expanders, could one simplify Gromov’s construction ? Answer: one needs large girth, so the Lubotzky-Phillips-Sarnak examples have to be used, [LPS].

**2. The Novikov conjecture **

Definition 5The be a finitely generated group. Let be a closed oriented -manifold with a map (classifying space of ). Let denote the homology fundamental class of , let denote Hirzebruch’s -class in cohomology. For consider the higher signature

The *Novikov conjecture* states that if is a homotopy equivalence of closed oriented manifolds. Then .

In 2000, Guoliang Yu, [Y], proved

Theorem 6 (Yu)If (the Cayley graph of) a group coarsely embeds in Hilbert space, then satisfies (NC).

*Proof:* The proof uses operator algebras.

- To every group, one associates the
*reduced -algebra*. - To every discrete metric space , one associates the
*Roe algebra*.

Yu’s proof goes through two other conjectures.

- (CBC) Coarse Baum-Connes conjecture: If is a discrete metric space with bounded geometry, theb the -theory of can be computed in terms of geometric data.
- (SNC) Strong Novikov conjecture: For a finitely generated group. The
*index map*from the -homology of to -theory of is injective.

Here is some history. In 1980, Kasparov and Mishchenko proved that (SNC) implies (NC), showing that (NC) is a problem in operator algebras rather than topology. In 1991, Higson and Roe proved that if the Cayley graph of satisfies (CBC), then satisfies (SNC). In 2000, Yu proved that if a Cayley graph coarsely embeds in Hilbert space, then it satisfies (CDC).

**3. Yu’s Property (A) **

** 3.1. Positive definite kernels **

Definition 7A kernel (i.e. a -variable function) on a set ispositive definiteif the matrix is positive definite for every .

Equivalently: There exists a Hilbert space and a map from to the unit sphere of such that .

Definition 8Let be a discrete metric space. Say has Property (A) if there exists a sequence of positive definite kernels such that

is supported in a bounded neighborhood of the diagonal.tends to uniformly on all .

Proposition 9If is a finitely generated amenable group, then has Property (A).

*Proof:* Let be the -ball centered at the origin. Pick a F\o lner set for , i.e.

Let be the normalized characteristic function of . Set

Then

if , i.e. .

Proposition 10Locally finite trees have Property (A).

*Proof:* Fix an end of . For , let denote the ray from to . Define , so that , and

Since in , is positive definite.

Fix . If , let be the median of , and . Note that . uniformly on .

** 3.2. Conditionally negative definite kernels **

Definition 11A kernel on isconditionally negative definiteiff for every , the matrix is positive definite on the hyperplane .

Equivalently: There exists a Hilbert space and a map such that .

Proposition 12 (Yu)If a graph metric space has Property (A), then it is coarsely embeddable in Hilbert space.

*Proof:* Mimic the proof of coarse embeddability of amenable groups. Let be positive definite kernels converging to at exponential speed, i.e.

By assumption, there is such that . Then . In particular, is conditionally negative definite. Set

This is again conditionally negative definite, so it comes from a Hilbertian embedding . Let us check that is a coarse embedding. Set

This is proper. Indeed, if , then for , , so .

The first examples of graphs coarsely embeddable into Hilbert space but not satisfying Property (A) are due to Piotr Nowak (2006). They do not have bounded geometry. Examples with bounded geometry have been constructed by Arzhantseva, Guentner and Spakula in 2011. Here is the construction. Start with a group . The group generated by all squares is normal. Iterate times to get . Then the example is . These are finite -groups.

Linial: these are iterated lifts.

Property (A) fails here thanks to the

Theorem 13 (Roe)Let be a finitely generated, residually finite group. Let be decreasing normal subgroups with . The is amenable iff has Property (A).

Proving that the examples coarsely embed is not easy.

** References **

[LLR] Linial, Nathan; London, Eran; Rabinovich, Yuri; * The geometry of graphs and some of its algorithmic applications.* Combinatorica **15** (1995), no. 2, 215–245.

[LPS] Lubotzky, Alex; Phillips, R.; Sarnak, Peter; * Ramanujan graphs.* Combinatorica **8** (1988), no. 3, 261–277.

[M] Margulis, Grigorii; * Explicit constructions of expanders.* Problemy Pereda\v ci Informacii **9** (1973), no. 4, 71–80.

[Y] Yu, Guolian; * The coarse Baum-Connes conjecture for spaces which admit a uniform embedding into Hilbert space.* Invent. Math. **139** (2000), no. 1, 201–240.