# Mathematics Colloquium

#### Quantitative Behavior of Lipschitz Maps from the Heisenberg Group to $$L^1$$

Speaker: Jeff Cheeger, New York University, Courant Institute of Mathematical Sciences

Location: Warren Weaver Hall 1302

Date: Monday, February 9, 2009, 3:45 p.m.

Synopsis:

Let $$\left ( X, d \right )$$ denote a metric space and let $$\mathcal{C}$$ denote a collection of metrics on $$X$$ such that $${d}' \in \mathcal{C}$$ implies $$c \cdot {d}' \in \mathcal{C}$$, for any real number $$c > 0$$. Put

$$\rho \left ( d, \mathcal{C} \right ) = \inf_{{d}' \in \mathcal{C}} \inf \left \{ c \mid {d}' \leq d \leq c \cdot {d}' \right \}.$$

Let $$\mathcal{L}$$ denote the collection of metrics on $$X$$ of the form, $${d}' \left ( x_1, x_2 \right ) = \left \| f \left ( x_1 \right ) - f \left ( x_2 \right ) \right \|_{L_1}$$, for some map $$f : X \rightarrow L^1$$ and let $$\mathcal{N}$$ denote the collection of metrics $$\underline{d}$$ on $$X$$ such that $$\left ( X, \underline{d}^{\frac{1}{2}} \right )$$ embeds isometrically in $$L^2$$. It is easy to verify that $$\mathcal{C} \subset \mathcal{N}$$, and so, $$\rho \left ( d , \mathcal{N} \right ) \leq \rho \left ( \mathcal{L} \right )$$. If $$X$$ is finite with cardinality $$n$$, it was shown by Bourgain that $$\rho \left ( d , \mathcal{L} \right ) = O \left ( \log n \right )$$, for any metric $$d$$.

Although the problem of computing $$\rho \left ( d , \mathcal{L} \right )$$ exactly is equivalent to various other fundamental problems for which there is believed to be no polynomial time algorithm, there is a polynomial time algorithm for computing $$\rho \left ( d , \mathcal{N} \right )$$. Goemans and Linial conjectured that for some universal constant $$C > 0$$, independent of $$n$$,

$$\rho \left ( d , \mathcal{N} \right ) \leq C \cdot \rho \left ( d , \mathcal{L} \right ).$$

Their conjecture was refuted by Khot-Vishnoi (2005) who gave a sequence of examples for which the best $$C$$ grows at least like a constant times $$\log \log n$$. We will discuss a very different sequence based on the Heisenberg group, for which $$C$$ grows at least like $$\left ( \log n \right )^{a}$$, for some explicit $$a > 0$$. This is joint work with Kleiner and Naor. It is an outgrowth of earlier work of Lee-Naor and Cheeger-Kleiner.