Limitations to Fréchet's metric embedding method (Q2382346): Difference between revisions

The paper is devoted to low-distortion embeddings of finite metric spaces into the Banach spaces \(\ell_p\) \((1\leq p<\infty)\). The distortion of an (injective) embedding \(f:X\to\ell_p\) is defined as the product of the Lipschitz constants \(\text{Lip}(f)\cdot\text{Lip}(f^{-1}|_{f(X)})\). The authors define a Fréchet embedding as an embedding \(f:X\to\ell_p^S\) (\(S\) is the set of all nonempty subsets of \(X\)) given by \[ f(x)=\{\alpha_A\cdot\text{distance}(x,A)\}_{A\in S}, \] where \(\alpha_A\) are some real numbers (usually assumed to be non-negative). Such embeddings play a significant role in the theory [see \textit{J. Bourgain}, Isr. J. Math. 52, 46--52 (1985; Zbl 0657.46013); \textit{S. Rao}, ``Small distortion and volume preserving embeddings for planar and Euclidean metrics'', in: Proceedings of the Fifteenth Annual Symposium on Computational Geometry (Miami Beach, FL, 1999), 300--306 (electronic), ACM, New York (1999; Zbl 0993.68504)]. The problem considered in this paper is inspired by the recent studies on Ramsey type problems of the following type: given a finite metric space, a how large subset of it has a small-distortion embedding into \(\ell_2\)? See \textit{M. Mendel} and \textit{A. Naor} [J.~Eur. Math. Soc. 9, No. 2, 253--275 (2007; Zbl 1122.68043)] for an important recent Ramsey type result and references. The point is that in the recent achievements on Ramsey type problems Fréchet embeddings are not used, instead they use approximations of metrics based on hierarchically well-separated trees introduced by \textit{Y. Bartal} [``Probabilistic approximation of metric spaces and its algorithmic applications'', in: 37th Annual Symposium on Foundations of Computer Science (Burlington, VT, 1996), 184--193, IEEE Comput. Soc. Press, Los Alamitos, CA (1996)]. The main result of the present paper (Theorem 2) shows that it is not coincidental: some of the known Ramsey type results cannot be achieved using Fréchet embeddings. The presentation of the main result is self-contained. The final section of the paper contains comments on relations between ultrametrics and dominated \(\ell_1\) metrics introduced by \textit{J. Matoušek} and \textit{Y. Rabinovich} [Isr. J. Math. 123, 285--301 (2001; Zbl 0987.46022)].