**1. Embedding finite metric spaces into Hilbert spaces **

Definition 1Let be a map between metric spaces. The Lipschitz norm of isand the

distorsionof 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 ,

so

If is -Lipschitz, the right hand side is bounded, the left hand side bounds the observable diameter, thus

Proposition 5The observable diameter is bounded on expanding families of graphs.

Since volume growth is at most , the typical distance in is , thus, for arbitrary maps ,

and

leading to

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 7Say a family of metric spaces satisfies asingle scale obstructionif 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 8Let . An-ensembleis 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.

Theorem 9 (Gupta, Krauthgamer, Lee)

- 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.

Theorem 10 (Lee 2005)If admits an -ensemble, then

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 12Define the modulus of decomposability of as

Example 2.

Example 3For 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 .

Since

we can assume that no radius is too big.

Lemma 14

*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.

** 2.6. Comments **

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.