Distortion of embeddings of binary trees into diamond graphs
HTML articles powered by AMS MathViewer
- by Siu Lam Leung, Sarah Nelson, Sofiya Ostrovska and Mikhail Ostrovskii PDF
- Proc. Amer. Math. Soc. 146 (2018), 695-704 Request permission
Abstract:
Diamond graphs and binary trees are important examples in the theory of metric embeddings and also in the theory of metric characterizations of Banach spaces. Some results for these families of graphs are parallel to each other; for example superreflexivity of Banach spaces can be characterized both in terms of binary trees (Bourgain, 1986) and diamond graphs (Johnson-Schechtman, 2009). In this connection, it is natural to ask whether one of these families admits uniformly bilipschitz embeddings into the other. This question was answered in the negative by Ostrovskii (2014), who left it open to determine the order of growth of the distortions. The main purpose of this paper is to get a sharp up-to-a-logarithmic-factor estimate for the distortions of embeddings of binary trees into diamond graphs and, more generally, into diamond graphs of any finite branching $k\ge 2$. Estimates for distortions of embeddings of diamonds into infinitely branching diamonds are also obtained.References
- F. Baudier, R. Causey, S. J. Dilworth, D. Kutzarova, N. L. Randrianarivony, Th. Schlumprecht, and S. Zhang, On the geometry of the countably branching diamond graphs, J. Funct. Anal., to appear, https://doi.org/10.1016/j.jfa.2017.05.013
- J. A. Bondy and U. S. R. Murty, Graph theory, Graduate Texts in Mathematics, vol. 244, Springer, New York, 2008. MR 2368647, DOI 10.1007/978-1-84628-970-5
- J. Bourgain, The metrical interpretation of superreflexivity in Banach spaces, Israel J. Math. 56 (1986), no. 2, 222–230. MR 880292, DOI 10.1007/BF02766125
- Bo Brinkman and Moses Charikar, On the impossibility of dimension reduction in $l_1$, J. ACM 52 (2005), no. 5, 766–788. MR 2176562, DOI 10.1145/1089023.1089026
- Anupam Gupta, Ilan Newman, Yuri Rabinovich, and Alistair Sinclair, Cuts, trees and $l_1$-embeddings of graphs, Combinatorica 24 (2004), no. 2, 233–269. MR 2071334, DOI 10.1007/s00493-004-0015-x
- William B. Johnson and Gideon Schechtman, Diamond graphs and super-reflexivity, J. Topol. Anal. 1 (2009), no. 2, 177–189. MR 2541760, DOI 10.1142/S1793525309000114
- Benoît R. Kloeckner, Yet another short proof of Bourgain’s distortion estimate for embedding of trees into uniformly convex Banach spaces, Israel J. Math. 200 (2014), no. 1, 419–422. MR 3219585, DOI 10.1007/s11856-014-0024-4
- J. R. Lee and A. Naor, Embedding the diamond graph in $L_p$ and dimension reduction in $L_1$, Geom. Funct. Anal. 14 (2004), no. 4, 745–747. MR 2084978, DOI 10.1007/s00039-004-0473-8
- James R. Lee and Prasad Raghavendra, Coarse differentiation and multi-flows in planar graphs, Discrete Comput. Geom. 43 (2010), no. 2, 346–362. MR 2579701, DOI 10.1007/s00454-009-9172-4
- Ilan Newman and Yuri Rabinovich, A lower bound on the distortion of embedding planar metrics into Euclidean space, Discrete Comput. Geom. 29 (2003), no. 1, 77–81. MR 1946795, DOI 10.1007/s00454-002-2813-5
- Mikhail I. Ostrovskii, On metric characterizations of some classes of Banach spaces, C. R. Acad. Bulgare Sci. 64 (2011), no. 6, 775–784. MR 2884975
- Mikhail I. Ostrovskii, Metric embeddings, De Gruyter Studies in Mathematics, vol. 49, De Gruyter, Berlin, 2013. Bilipschitz and coarse embeddings into Banach spaces. MR 3114782, DOI 10.1515/9783110264012
- Mikhail Ostrovskii, Metric characterizations of superreflexivity in terms of word hyperbolic groups and finite graphs, Anal. Geom. Metr. Spaces 2 (2014), no. 1, 154–168. MR 3210894, DOI 10.2478/agms-2014-0005
- Mikhail Ostrovskii and Beata Randrianantoanina, Metric spaces admitting low-distortion embeddings into all $n$-dimensional Banach spaces, Canad. J. Math. 68 (2016), no. 4, 876–907. MR 3518997, DOI 10.4153/CJM-2015-041-7
- Mikhail I. Ostrovskii and Beata Randrianantoanina, A new approach to low-distortion embeddings of finite metric spaces into non-superreflexive Banach spaces, J. Funct. Anal. 273 (2017), no. 2, 598–651. MR 3648862, DOI 10.1016/j.jfa.2017.03.017
- Gilles Pisier, Martingales in Banach spaces, Cambridge Studies in Advanced Mathematics, vol. 155, Cambridge University Press, Cambridge, 2016. MR 3617459
- Y. Rabinovich and R. Raz, Lower bounds on the distortion of embedding finite metric spaces in graphs, Discrete Comput. Geom. 19 (1998), no. 1, 79–94. MR 1486638, DOI 10.1007/PL00009336
- Oded Regev, Entropy-based bounds on dimension reduction in $L_1$, Israel J. Math. 195 (2013), no. 2, 825–832. MR 3096576, DOI 10.1007/s11856-012-0137-6
Additional Information
- Siu Lam Leung
- Affiliation: Department of Mathematical Sciences, Kent State University, Kent, Ohio 44242
- MR Author ID: 1045241
- Email: sleung1@kent.edu
- Sarah Nelson
- Affiliation: Department of Mathematics and Statistics, Hunter College, CUNY, New York, New York 10065
- Email: sarah.nelson07@yahoo.com
- Sofiya Ostrovska
- Affiliation: Department of Mathematics, Atilim University, 06836 Incek, Ankara, Turkey
- MR Author ID: 329775
- Email: sofia.ostrovska@atilim.edu.tr
- Mikhail Ostrovskii
- Affiliation: Department of Mathematics and Computer Science, St. John’s University, 8000 Utopia Parkway, Queens, New York 11439
- MR Author ID: 211545
- Email: ostrovsm@stjohns.edu
- Received by editor(s): August 8, 2016
- Received by editor(s) in revised form: March 28, 2017
- Published electronically: August 30, 2017
- Communicated by: Thomas Schlumprecht
- © Copyright 2017 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 146 (2018), 695-704
- MSC (2010): Primary 46B85; Secondary 05C12, 30L05
- DOI: https://doi.org/10.1090/proc/13750
- MathSciNet review: 3731702