Ramsey-like properties for bi-Lipschitz mappings of finite metric spaces

Matoušek, Jiří

Commentationes Mathematicae Universitatis Carolinae, Tome 33 (1992) no. 3, pp. 451-463.

Résumé

Let $(X,\rho)$, $(Y,\sigma)$ be metric spaces and $f:X\to Y$ an injective mapping. We put $\|f\|_{Lip} = \sup \{\sigma (f(x),f(y))/\rho(x,y)$; $x,y\in X$, $x\neq y\}$, and $\operatorname{dist}(f)= \|f\|_{Lip}.\|f^{-1}\|_{Lip}$ (the {\sl distortion\/} of the mapping $f$). Some Ramsey-type questions for mappings of finite metric spaces with bounded distortion are studied; e.g., the following theorem is proved: Let $X$ be a finite metric space, and let $\varepsilon>0$, $K$ be given numbers. Then there exists a finite metric space $Y$, such that for every mapping $f:Y\to Z$ ($Z$ arbitrary metric space) with $\operatorname{dist}(f)$ one can find a mapping $g:X\to Y$, such that both the mappings $g$ and $f|_{g(X)}$ have distortion at most $(1+\varepsilon)$. If $X$ is isometrically embeddable into a $\ell_p$ space (for some $p\in [1,\infty]$), then also $Y$ can be chosen with this property.

Détail

Classification : 05C55, 05D10, 54C25, 54E35
Keywords: Ramsey theory; embedding of metric spaces; distortion; Lipschitz mapping; differentiability of Lipschitz mappings