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 1 Let be a family of finite collected, -regular graphs, with increasing size. Say that is a family of expanders if 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 3 is 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 4 Let 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
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 5 The 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 7 A kernel (i.e. a -variable function) on a set is positive definite if 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 8 Let 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 9 If 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
if , i.e. .
Proposition 10 Locally 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 11 A kernel on is conditionally negative definite iff 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.