1. Coarse embeddings into Hilbert spaces
In 1993, motivated by an approach suggested by Connes to Novikov conjecture, Gromov suggested to investigate coarse embeddings of groups in Hilbert space .
Definition 1 Let be a metric space. A map is a coarse embedding if distances in the range and in the domain tend to infinity simultaneously (each is bounded by a function of the other).
Question: does every separable metric space admit such embeddings ?
A counterexample was soon obtained. It is based on old work of Per Enflo. Since anay metric space embeds isometrically in some , it is natural to look there for a counterexample.
Theorem 2 (Dranishnikov-Lafforgue-Yu) The sequence does not coarsely embed into .
Easy to discretize and organize into a graph. Drawback: degree of vertices is unbounded.
In 2000, Gromov improved the example to get bounded degree graphs, using an expander.
Definition 3 An expander is a sequence of finite graphs whose size tends to infinity, degree stays bounded, but Cheeger constant
stays bounded below.
Example. Large squares do not form an expander. Indeed, cutting in half requires only linear boundary. Trees do not either: cutting one edge suffices to split in half.
So it is not that easy to produce examples of expanders. Until 2000, the only known sources were
- Random graphs (Kolmogorov-Barzdin 1960’s, Pinsker 1973).
- Group theory (Margulis 1973).
3. Expanders versus embeddings
An alternate characterization of expanders was given by N. Alon in 1986.
Theorem 4 (Alon) The sequence is an expander iff it has a uniform spectral gap, i.e. for all and for every real valued function on ,
Corollary 5 An expander does not coarsely embed into .
Indeed, a coarse embedding is -Lipschitz. The spectral gap provides us with a point such that
where is the degree. A positive proportion of points of satisfy . But, under a coarse embedding, the size of the inverse image of balls of fixed radius is bounded, contradiction.
Corollary 6 A metric space that weakly contains an expander does not coarsely embed into .
Weakly contains means is -Lipschitz and inverse images of points represent a decaying proportion of points of .
Question. Conversely, if a bounded degree graph does not coarsely embed into , does it weakly contain an expander ?
4. Expanders from group theory
4.1. Property (T)
Definition 7 Let be a finitely generated group. Say has property (T) if every isometric affine action of on a Hilbert space has bounded orbits ( has a fixed point).
Examples. Infinite solvable (more generally, amenable) groups are not (T). Free groups are not (T). Lattices in higher rank simple Lie groups, e.g. , are (T).
Pick a generating system for . Take . Then get large and have degree bounded above by . I claim that have a uniform spectral gap.
4.2. A lemma
Fact. Let be a property (T) group with generating system . There exists such that for every unitary representation and any cocycle ,
Proof is by contradiction. Otherwise, get sequence , with on but tends to infinity. Form the direct sum , set . Then the corresponding affine isometric action has unbounded orbits.
4.3. Spectral gap for
View , with action on the right, as a unitary representation of . Take direct sum. Define cocycle by
for . Then
Furthermore, previous lemma yields
Averaging over yields the spectral gap (also known as Poincaré) inequality.
Note that the same argument would apply to amenable quotients of , instead of finite ones.