Distortion of embeddings of binary trees into diamond graphs

Leung, Siu Lam; Nelson, Sarah; Ostrovska, Sofiya; Ostrovskii, Mikhail

doi:10.1090/proc/13750

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