Metric Spaces Admitting Low-distortion Embeddings into All n-dimensional Banach Spaces

Ostrovskii, Mikhail ; Randrianantoanina, Beata

Canadian journal of mathematics, Tome 68 (2016) no. 4, pp. 876-907

Résumé

For a fixed $K\,\gg \,1$ and $n\,\in \,\mathbb{N}$ , $n\,\gg \,1$ we study metric spaces which admit embeddings with distortion $\le \,K$ into each $n$ -dimensional Banach space. Classical examples include spaces embeddable into log $n$ -dimensional Euclidean spaces, and equilateral spaces.We prove that good embeddability properties are preserved under the operation of metric composition of metric spaces. In particular, we prove that $n$ -point ultrametrics can be embedded with uniformly bounded distortions into arbitrary Banach spaces of dimension $\log \,n$ .The main result of the paper is a new example of a family of finite metric spaces which are not metric compositions of classical examples and which do embed with uniformly bounded distortion into any Banach space of dimension $n$ . This partially answers a question of G. Schechtman.

Détail

DOI : 10.4153/CJM-2015-041-7

Mots-clés : 46B85, 05C12, 30L05, 46B15, 52A21, basis constant, bilipschitz embedding, diamond graph, distortion, equilateral set, ultrametric

Bibliographie

[AB14] [AB14] Albiac, JF. and Baudier, F., Embeddabtlity of snowfiaked metrics with applications to thenonlinear geometry of the spaces L and l for 0 < p < ∞. J. Geom. Anal. 25(2015), no. 1, 1–24. Google Scholar | DOI

[AM83] [AM83] Alon, N. and Milman, V. D., Embedding of lk∞ in finite-dimensional Banach spaces. Israel J. Math. 45(1983), no. 4, 265–280. Google Scholar | DOI

[ABV98] [ABV98] Arias-de-Reyna, J., Ball, K., and Villa, R., Concentration of the distance infinite-dimensional normed spaces. Mathematika 45(1998), no. 2, 245–252. http://dx.doi.Org/10.1112/SOO255793OOO14182 Google Scholar

[Ass83] [Ass83] Assouad, P., Plongements lipschitziens dansRn. Bull. Soc. Math. France 111(1983), no. 4, 429–448. Google Scholar

[Bar96] [Bar96] Bartal, Y., Probabilistic approximation of metric spaces and its algorithmic applications. In: The 37th Annual Symposium on Foundations of Computer Science, IEEE Comput. Sci. Press, Los Alamitos, CA, 1996, pp. 184–193. Google Scholar

[Bar99] [Bar99] Bartal, Y., On approximating arbitrary metrices by tree metrics. STOC '98 (Dallas, TX), ACM, New York, 1999, pp. 161–168. Google Scholar

[BLMN04] [BLMN04] Bartal, Y., Linial, N., Mendel, M., and Naor, A., Low dimensional embeddings of ultrametrics. European J. Combin. 25(2004), no. 1, 87–92. http://dx.doi.Org/10.1016/j.ejc.2OO3.O8.OO3 Google Scholar

[BLMN05] [BLMN05] Bartal, Y., On metric Ramsey-type phenomena. Annals of Math. 162(2005), 643–709. Google Scholar | DOI

[BM04] [BM04] Bartal, Y. and Mendel, M., Dimension reduction for ultrametrics. In: Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, 2004, pp. 664–665. Google Scholar

[BB91] [BB91] Bastero, J. and Bernué, J., Applications of deviation inequalities on finite metric sets. Math. Nachr. 153(1991), 33–41. http://dx.doi.Org/10.1002/mana.19911530104 Google Scholar

[BBK89] [BBK89] Bastero, J., Bernué;s, J., and Kalton, N., Embedding ln∞-cubes in finite-dimensional 1-subsymmetric spaces. Rev. Mat. Univ. Complut. Madrid 2 (1989), suppl., 47–52. Google Scholar

[BPS95] [BPS95] Bastero, J., Peña, A., and Schechtman, G.,Embedding ln∞-cubes in low-dimensional Schatten classes. Geometric aspects of functional analysis (Israel, 1992-1994), 5-11, Oper. Theory Adv.Appl., 77, Birkhâuser, Basel, 1995. Google Scholar

[BFM86] [BFM86] Bourgain, J., Figiel, T., and Milman, V., On Hilbertian subsets of finite metric spaces. Israel J. Math. 55(1986), no. 2, 147–152. Google Scholar | DOI

[DS13] [DS13] David, G. and Snipes, M., A non-probabilistic proof ofthe Assouad embedding theorem with bounds on the dimension. Anal. Geom. Metr. Spaces 1(2013), 36–41. Google Scholar

[Dvo61] [Dvo61] Dvoretzky, A., Some results on convex bodies and Banach spaces. In: Proc. Internat. Sympos Linear Spaces (Jerusalem, 1960), pp. 123–160, Jerusalem Academic Press, Jerusalem; Pergamon, Oxford, 1961; Announcement: A theorem on convex bodies and applications to Banach spaces, Proc. Nat. Acad. Sci. U.S.A., 45 (1959) 223-226; erratum, 1554. Google Scholar

[FL94] [FL94] Füredi, Z. and Loeb, P. A., On the best constant for the Besicovitch covering theorem. Proc.Amer. Math. Soc. 121(1994), no. 4,1063–1073 Google Scholar | DOI

[Glu81] [Glu81] Gluskin, E. D., The diameter of the Minkowski compactum is roughly equal to n. (Russian) Funktsional. Anal, i Prilozhen. 15(1981), no. 1, 72–73. http://dx.doi.Org/10.1007/BF01082381 Google Scholar

[GNRS04] [GNRS04] Gupta, A., Newman, I., Rabinovich, Y., and Sinclair, A., Cuts, trees and l\-embeddings of graphs. Combinatorica 24(2004) 233–269. http://dx.doi.Org/10.1007/s00493-004-0015-x Google Scholar

[HeiOl] [HeiOl] Heinonen, J. M., Lectures on Analysis on Metric Spaces, Universitext, Springer-Verlag, NewYork, 2001. Google Scholar

[HeiO3] [HeiO3] Heinonen, J. M., Geometric embeddings of metric spaces. Report. University of Jyvâskylâ Department of Mathematics and Statistics, 90. University of Jyvâskylâ, Jyvâskylâ, 2003. http://www.math.jyu.fi/research/reports/rep90.pdf. Google Scholar

[Hugl2] [Hugl2] Hughes, B., Trees, ultrametrics, and noncommutative geometry. Pure Appl. Math. Q. 8(2012), no. 1, 221–312. Google Scholar | DOI

[JS09] [JS09] Johnson, W. B. and Schechtman, G., Diamond graphs and super-reflexivity. J. Topol. Anal. 1(2009), no. 2, 177–189. Google Scholar | DOI

[LPOl] [LPOl] Lang, U. and Plaut, C., Bilipschitz embeddings of metric spaces into space forms. Geom.Dedicata 87(2001), no. 1–3, 285-307. http://dx.doi.Org/10.1023/A:1012093209450 Google Scholar

[MT93] [MT93] Mankiewicz, P. and Tomczak-Jaegermann, N., Embedding subspaces ofln∞ into spaces withSchauder basis. Proc. Amer. Math. Soc. 117(1993), no. 2, 459–465. Google Scholar

[MN13] [MN13] Mendel, M. and Naor, A., Ultrametric subsets with large Hausdorff dimension. Invent. Math. 192(2013), no. 1, 1–54. Google Scholar | DOI

[Mil71] [Mil71] Milman, V. D., A new proof of A. Dvoretzky's theorem on cross-sections of convex bodies. (Russian) Funktsional. Anal, i Prilozhen. 5(1971), no. 4, 28–37. Google Scholar

[Mil85] [Mil85] Milman, V. D., Almost Euclidean quotient spaces of subspaces of a finite-dimensional normedspace. Proc. Amer. Math. Soc. 94(1985), no. 3, 445–449 Google Scholar | DOI

[NN12] [NN12] Naor, A. and Neiman, O., Assouad's theorem with dimension independent of the snowflaking. Rev. Mat. Iberoam. 28(2012), no. 4,1123–1142. http://dx.doi.Org/10.4171/RMI/706 Google Scholar

[Ostl4] [Ostl4] Ostrovskii, M. I., Metric characterizations of superreflexivity in terms of word hyperbolic groups and finite graphs. Anal. Geom. Metr. Spaces 2(2014), 154–168. Google Scholar | DOI

[Rud95] [Rud95] Rudelson, M., Estimates of the weak distance between finite-dimensional Banach spaces. Israel J. Math. 89(1995), no. 1-3, 189–204. http://dx.doi.Org/10.1007/BF02808200 Google Scholar

[Sch84] [Sch84] Schikhof, W. H., Ultrametric calculus. An introduction to p-adic analysis. Cambridge Studies in Advanced Mathematics, 4. Cambridge University Press, Cambridge, 1984. Google Scholar

[Sem99] [Sem99] Semmes, S., Bilipschitz embeddings of metric spaces into Euclidean spaces. Publ. Mat. 43(1999), no. 2, 571–653. Google Scholar | DOI

[ShkO4] [ShkO4] Shkarin, S. A., Isometric embedding of finite ultrametric spaces in Banach spaces. Topology Appl. 142(2004), no. 1-3, 13–17. http://dx.doi.Org/10.1016/j.topol.2003.12.002 Google Scholar

[Sza83] [Sza83] Szarek, S. J., The finite-dimensional basis problem with an appendix on nets of Grassmann manifolds.Acta Math. 151(1983), no. 3-4,153–179. http://dx.doi.Org/10.1007/BF02393205 Google Scholar

[ST09] [ST09] Szarek, S. J. and Tomczak-Jaegermann, N., On the nontrivial projection problem. Adv. Math. 221(2009), no. 2, 331–342. http://dx.doi.Org/10.1016/j.aim.2008.12.004 Google Scholar

[Tal95] [Tal95] Talagrand, M., Embedding of 𝓵k and a theorem of Alon and Milman. Geometric aspects of functional analysis (Israel, 1992-1994), 289–293, Oper. Theory Adv. Appl, 77, Birkhâuser,Basel, 1995. Google Scholar