Abstract
We investigate the minimum dimensionk such that anyn-point metric spaceM can beD-embedded into somek-dimensional normed spaceX (possibly depending onM), that is, there exists a mappingf: M→X with
Extending a technique of Arias-de-Reyna and Rodríguez-Piazza, we prove that, for any fixedD≥1,k≥c(D)n 1/2D for somec(D)>0. For aD-embedding of alln-point metric spaces into the samek-dimensional normed spaceX we find an upper boundk≤12Dn 1/[(D+1)/2]lnn (using thel k∞ space forX), and a lower bound showing that the exponent ofn cannot be decreased at least forD∃[1,7)∪[9,11), thus the exponent is in fact a jumping function of the (continuously varied) parameterD.
Similar content being viewed by others
References
[AFR85] N. Alon, P. Frankl and V. Rödl,Geometrical realization of set systems and probabilistic communication complexity, Proc. 26th IEEE Symposium on Foundations of Computer Science, 1985, pp. 277–280.
[AR92] J. Arias-de-Reyna and L. Rodríguez-Piazza,Finite metric spaces needing high dimension for Lipschitz embeddings in Banach spaces, Israel Journal of Mathematics79 (1992), 103–113.
[Ben66] C. T. Benson,Minimal regular graphs of girth eight and twelve, Canadian Journal of Mathematics18 (1966), 1091–1094.
[Big74] N. Biggs,Algebraic Graph Theory, Cambridge University Press, 1974.
[Bol78] B. Bollobás,Extremal Graph Theory, Academic Press, London, 1978.
[Bou85] J. Bourgain,On Lipschitz embedding of finite metric spaces in Hilbert space, Israel Journal of Mathematics52 (1985), 46–52.
[Bou86] J. Bourgain,The metrical interpretation of superreflexivity in Banach spaces, Israel Journal of Mathematics56 (1986), 222–230.
[BMW86] J. Bourgain, V. Milman and H. Wolfson,On type of metric spaces, Transactions of the American Mathematical Society294 (1986), 295–317.
[Gru67] B. Grünbaum,Convex Polytopes, John Wiley & Sons, London, 1967.
[JL84] W. Johnson and J. Lindenstrauss,Extensions of Lipschitz maps into a Hilbert space, Contemporary Mathematics26 (Conference in Modern Analysis and Probability), American Mathematical Society, 1984, pp. 189–206.
[JLS87] W. Johnson, J. Lindenstrauss and G. Schechtman,On Lipschitz embedding of finite metric spaces in low dimensional normed spaces, inGeometrical Aspects of Functional Analysis (J. Lindenstrauss and V. D. Milman, eds.), Lecture Notes in Mathematics1267, Springer-Verlag, Berlin-Heidelberg, 1987.
[LLR94] N. Linial, E. London and Yu. Rabinovich,The geometry of graphs and some of its algorithmic applications, Proceedings of the 35th IEEE Symposium on Foundations of Computer Science (1994), pp. 577–591. Journal version: Combinatorica15 (1995), 215–245.
[LPS88] A. Lubotzky, R. Phillips and P. Sarnak,Ramanujan graphs, Combinatorica8 (1988), 261–277.
[Ma90] J. Matoušek,Bi-Lipschitz embeddings into low-dimensional Euclidean spaces, Commentationes Mathematicae Universitatis Carolinae31 (1990), 589–600.
[Ma91] J. Matoušek,Note on bi-Lipschitz embeddings into normed spaces, Commentationes Mathematicae Universitatis Carolinae33 (1992), 51–55.
[Mil64] J. Milnor,On the betti numbers of real algebraic varieties, Proceedings of the American Mathematical Society15 (1964), 275–280.
[Tho65] R. Thom,Sur l’homologie des variétés algébriques reélles, inDifferential and Combinatorial Topology (S. S. Cairns, ed.), Princeton Univ. Press, 1965.
Author information
Authors and Affiliations
Corresponding author
Additional information
The research was supported by Charles University grant No. 351, by Czech Republic Grant GAČR 201/93/2167 and by EC Cooperative Action IC-1000 (project ALTEC:Algorithms for Future Technologie).
Rights and permissions
About this article
Cite this article
Matoušek, J. On the distortion required for embedding finite metric spaces into normed spaces. Israel J. Math. 93, 333–344 (1996). https://doi.org/10.1007/BF02761110
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF02761110