Note on bi-Lipschitz embeddings into normed spaces

Matoušek, Jiří

Commentationes Mathematicae Universitatis Carolinae, Tome 33 (1992) no. 1, pp. 51-55.

Résumé

Let $(X,d)$, $(Y,\rho)$ be metric spaces and $f:X\to Y$ an injective mapping. We put $\|f\|_{\operatorname{Lip}} = \sup \{\rho (f(x),f(y))/d(x,y); x,y\in X, x\neq y\}$, and $\operatorname{dist}(f)= \|f\|_{\operatorname{Lip}}.\| f^{-1}\|_{\operatorname{Lip}}$ (the {\sl distortion} of the mapping $f$). We investigate the minimum dimension $N$ such that every $n$-point metric space can be embedded into the space $\ell_{\infty }^N$ with a prescribed distortion $D$. We obtain that this is possible for $N\geq C(\log n)^2 n^{3/D}$, where $C$ is a suitable absolute constant. This improves a result of Johnson, Lindenstrauss and Schechtman [JLS87] (with a simpler proof). Related results for embeddability into $\ell_p^N$ are obtained by a similar method.

Détail

Classification : 46B07, 46B20, 46B25, 46B99, 54C25, 54E35
Keywords: finite metric space; embedding of metric spaces; distortion; Lipschitz mapping; spaces $\ell_p$