Ji\v {r}\'{\i } Matou\v {s}ek
Ramsey-like properties for bi-Lipschitz mappings of finite metric spaces

Comment.Math.Univ.Carolinae 33,3 (1992) 451-463.

Abstract: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 $dist(f)= ||f||_{Lip}.||f^{-1}||_{Lip}$ (the {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 $dist(f)<K$ 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.

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