Euclidean quotients of finite metric spaces (Q1763640): Difference between revisions

For \(\alpha>1\) and \(n\) an integer, one may enquire about the largest integer \(m\), denoted here by \(S_2(\alpha,n)\), such that any metric space of cardinality \(n\) has a subspace of cardinality \(m\) which \(\alpha\)-embeds into a Hilbert space. A study of the asymptotic behaviour of \(S_2(\alpha,n)\) was made by \textit{Y.~Bartal, N.~Linial} and \textit{M.~Mendel} [Ann.\ Math.\ (2) 162, No.~2, 643--709 (2005; Zbl 1114.46007)], marking another step in extending the local theory of Banach spaces to the setting of general metric spaces. Replacing the word ``subspace'' by ``quotient'', ``subspace of quotient'', or ``quotient of subspace'', leads to three new parameters, \(Q_2(\alpha,n)\), \(SQ_2(\alpha,n)\), and \(QS_2(\alpha,n)\), which are studied in detail here. (The case \(\alpha=1\) corresponds to isometric embeddings, which are not studied here.) All three parameters are asymptotically proportional to \(n\) when \(\alpha>2\). When \(\alpha<2\), both \(SQ_2(\alpha,n)\) and \(QS_2(\alpha,n)\) grow like a power of \(n\), as does \(Q_2(\alpha,n)\) when \(\sqrt2<\alpha<2\). However, \(Q_2(\alpha,n)\) is bounded when \(\alpha<\sqrt2\). In all cases, the appropriate constants may depend on \(\alpha\). For embeddings into \(L_p\) spaces rather than Hilbert spaces, essentially the same conclusions hold, except in the case \(4^{1\over p}<\alpha<2\), which remains open. For the \(d\)-dimensional hypercube equipped with the Hamming metric, a sharper estimate is established: for any positive \(\varepsilon<1/2\), a quotient of a subspace of the hypercube containing more than \((1-\varepsilon )2^d\) points can only \(\alpha\)-embed in a Hilbert space if \(\alpha\) exceeds an absolute constant times \(\sqrt{b/\log(de/b)}\), where \(b=-\log\varepsilon\). More technical results are given for ultrametric spaces, and applications to computer science are promised in a subsequent paper. The authors work with the definition of quotient metric space from the book of \textit{M.~Gromov} [``Metric structures for Riemannian and non-Riemannian spaces'' (Progress in Mathematics 152, Birkhäuser, Boston) (1999; Zbl 0953.53002)], which differs from others in the literature. At the end of the paper, they show that Gromov's definition is the appropriate one to use in this context.