Abstract:Let $(X,d)$, $(Y,\rho )$ be metric spaces and $f:X\to Y$ an injective mapping. We put $||f||_{Lip} = \sup \{\rho (f(x),f(y))/d(x,y); x,y\in X, x\not =y\}$, and $dist(f)= ||f||_{Lip}.|| f^{-1}||_{Lip}$ (the {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.
Keywords: finite metric space, embedding of metric spaces, distortion, Lipschitz mapping, spaces $\ell _p$
AMS Subject Classification: 46B99, 54C25