Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

Request Permissions   Purchase Content 


Distortion of embeddings of binary trees into diamond graphs

Authors: Siu Lam Leung, Sarah Nelson, Sofiya Ostrovska and Mikhail Ostrovskii
Journal: Proc. Amer. Math. Soc. 146 (2018), 695-704
MSC (2010): Primary 46B85; Secondary 05C12, 30L05
Published electronically: August 30, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] 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,
  • [2] J. A. Bondy and U. S. R. Murty, Graph theory, Graduate Texts in Mathematics, vol. 244, Springer, New York, 2008. MR 2368647
  • [3] J. Bourgain, The metrical interpretation of superreflexivity in Banach spaces, Israel J. Math. 56 (1986), no. 2, 222-230. MR 880292,
  • [4] Bo Brinkman and Moses Charikar, On the impossibility of dimension reduction in $ l_1$, J. ACM 52 (2005), no. 5, 766-788. MR 2176562,
  • [5] 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,
  • [6] William B. Johnson and Gideon Schechtman, Diamond graphs and super-reflexivity, J. Topol. Anal. 1 (2009), no. 2, 177-189. MR 2541760,
  • [7] 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,
  • [8] 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,
  • [9] 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,
  • [10] 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,
  • [11] 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
  • [12] Mikhail I. Ostrovskii, Metric embeddings, Bilipschitz and coarse embeddings into Banach spaces, De Gruyter Studies in Mathematics, vol. 49, De Gruyter, Berlin, 2013. MR 3114782
  • [13] Mikhail Ostrovskii, Metric characterizations of superreflexivity in terms of word hyperbolic groups and finite graphs, Anal. Geom. Metr. Spaces 2 (2014), 154-168. MR 3210894,
  • [14] 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,
  • [15] 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,
  • [16] Gilles Pisier, Martingales in Banach spaces, Cambridge Studies in Advanced Mathematics, vol. 155, Cambridge University Press, Cambridge, 2016. MR 3617459
  • [17] 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,
  • [18] Oded Regev, Entropy-based bounds on dimension reduction in $ L_1$, Israel J. Math. 195 (2013), no. 2, 825-832. MR 3096576,

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 46B85, 05C12, 30L05

Retrieve articles in all journals with MSC (2010): 46B85, 05C12, 30L05

Additional Information

Siu Lam Leung
Affiliation: Department of Mathematical Sciences, Kent State University, Kent, Ohio 44242

Sarah Nelson
Affiliation: Department of Mathematics and Statistics, Hunter College, CUNY, New York, New York 10065

Sofiya Ostrovska
Affiliation: Department of Mathematics, Atilim University, 06836 Incek, Ankara, Turkey

Mikhail Ostrovskii
Affiliation: Department of Mathematics and Computer Science, St. John’s University, 8000 Utopia Parkway, Queens, New York 11439

Keywords: Binary tree, diamond graph, distortion of a bilipschitz embedding, Lipschitz map
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
Article copyright: © Copyright 2017 American Mathematical Society

American Mathematical Society