1. Embedding finite metric spaces into Hilbert spaces
Definition 1 Let be a map between metric spaces. The Lipschitz norm of is
and the distorsion of is . The -distorsion of is
We are interested is quantitative aspects in terms of . We shall see that this involves nice qualitative facts too.
Theorem 2 (Bourgain 1985) For finite, .
2. Obstructions to embeddability
2.1. Observable diameter
Let be a metric measure space (generalizes finite metric spaces with counting measure). Given a map , the essential diameter of is the minimum diameter of where contains at least 90% of the measure.
Definition 3 (Gromov)
This notion enters the following spectral considerations. Let be a -regular graph. The Laplacian is , adjacency matrix. The second eigenvalue is
Theorem 4 (Pinsker) There exists an expanding family, i.e. an infinite family of -regular graphs such that for all , .
On such a graph, for all ,
If is -Lipschitz, the right hand side is bounded, the left hand side bounds the observable diameter, thus
Proposition 5 The observable diameter is bounded on expanding families of graphs.
Since volume growth is at most , the typical distance in is , thus, for arbitrary maps ,
Theorem 6 (Linial, London, Rabinovich 1994) For an expanding family of -regular graphs,
2.2. Single scale obstruction
Expanding families satisfy the following stronger property, with .
Definition 7 Say a family of metric spaces satisfies a single scale obstruction if there exists such that for all -Lipschitz ,
We shall see that more subtle obstructions exist, which cannot be localized at one scale.
2.3. Multiscale obstruction
Suppose that does not satisfy a single scale obstruction. Then for all and all there exists a -Lipschitz map which, on average, distorts distances at scale by at most . An -ensemble requires this estimate to hold uniformly and not only on average. It is a tool for constructing embeddings.
Definition 8 Let . An -ensemble is a family of maps , , such that
- For , .
Example 1 (Laakso, Lang and Plaut) The Laakso spaces are graphs obtained by recursively replacing edges with 6-edge hinges.
- admits an -ensemble.
Proof: The Lebesgue differentiation theorem states that a Lipschitz curve in is close to a line at almost every point and at all small scales. This idea applies to geodesics in Laakso spaces. Since there are at least two pretty remote geodesics in between every pair of endpoints, this implies that compression occurs somewhere near the middle. This is formalized in the short diagonals lemma (as called by Matousek):
If a 6-edges hinge is mapped to Hilbert space with -distorsion of edges, then the two midpoints satisfy . So global distorsion is .
In this simple example, differentiation boils down to summing defects (in squared distance) over successive scales.
The next theorem shows that the distorsion lower bound for Laakso graphs in Theorem 9 is sharp.
If follows that spaces whose Hilbert distorsion is can admit -ensembles only if , i.e. satisfy a one scale obstruction.
The next theorem shows that Theorem 10 is sharp.
Theorem 11 (Jaffe, Lee, Moharrami 2009) There exists an -point space such that
- admits an -ensemble.
2.4. Random partitions
This is a tool to construct -ensembles.
Let be a random partition of , i.e. a distribution over partitions of . Denoting by the unique piece of containing , say that is -padded if
- All pieces of have diameter .
- For every ,
Definition 12 Define the modulus of decomposability of as
Example 2 .
Example 3 For hyperbolic space, , but if one considers only distances , .
Example 4 (Klein, Plotkin, Rao) For planar graphs, .
Based on the following. On a planar surface, take an -annulus, intersect with another -annulus, and again one more time. What you get is bounded independantly on . This is proven using the fact that does not embed in the plane. Does this fact appear in Riemannian geometry ?
Example 5 (Lee, Sidiropoulos) For surfaces of genus , .
2.5. Random partitions for general finite metric spaces
Proof: Given . Order points . Choose independant exponential random variables with parameter . Let be minus the previously defined . They form the pieces of random partition .
we can assume that no radius is too big.
Proof: of Lemma. One can assume that . Assume that for some , overlaps . From the memoryless property of the exponential distribution, conditioned on the above event, the distribution of is still exponential with same parameter, so the bad event ( only overlaps a little on instead of containing it) has probability
This completes the proof of Theorem 13.
In the sequel, we shall construct random partition tailored for special classes of metric spaces.
One can use Theorem 13, with some extra work, to prove Bourgain’s theorem, but Bourgain’s proof is simpler.
Lang: can one use Bourgain’s theorem to prove Theorem 13 ? Answer: yes, but with bound .
Question: find a direct proof of the fact that the observable diameter of every metric on the -sphere is bounded below by area. This is a strengthening of Joseph Hersch’s 1970 upper bound on spectral gap.