Article
Full entry |
PDF
(0.1 MB)
Feedback
PDF
(0.1 MB)
Feedback
Keywords:
finite metric space; embedding of metric spaces; distortion; Lipschitz mapping; spaces $\ell_p$
finite metric space; embedding of metric spaces; distortion; Lipschitz mapping; spaces $\ell_p$
Summary:
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.
References:
[Bou85] Bourgain J.: On Lipschitz embedding of finite metric spaces in Hilbert space. Israel J. Math. 52 (1985), 46-52. MR 0815600 | Zbl 0657.46013
[BMW86] Bourgain J., Milman V., Wolfson H.: On type of metric spaces. Trans. Amer. Math. Soc. 294 (1986), 295-317. MR 0819949 | Zbl 0617.46024
[JL84] Johnson W., Lindenstrauss J.: Extensions of Lipschitz maps into a Hilbert space. Contemporary Math. 26 (Conference in modern analysis and probability) 189-206, Amer. Math. Soc., 1984. MR 0737400
[JLS87] Johnson W., Lindenstrauss J., Schechtman G.: On Lipschitz embedding of finite metric spaces in low dimensional normed spaces. in: {\sl Geometrical aspects of functional analysis} (J. Lindenstrauss, V.D. Milman eds.), Lecture Notes in Mathematics 1267, Springer-Verlag, 1987. MR 0907694 | Zbl 0631.46016
[Ma89] Matoušek J.: Lipschitz distance of metric spaces (in Czech). CSc. degree thesis, Charles University, 1990.
[Scho38] Schoenberg I.J.: Metric spaces and positive definite functions. Trans. Amer. Math. Soc. 44 (1938), 522-536. MR 1501980 | Zbl 0019.41502
[Spe87] Spencer J.: Ten Lectures on the Probabilistic Method. CBMS-NSF, SIAM 1987. MR 0929258 | Zbl 0822.05060
Search
Partner of
