Nonexistence of embeddings with uniformly bounded distortions of Laakso graphs into diamond graphs

DOI10.1016/J.DISC.2016.08.003zbMATH Open1351.05154arXiv1512.06439OpenAlexW2963865481MaRDI QIDQ2374152FDOQ2374152

Authors: Sofiya Ostrovska, Mikhail Ostrovskii 

Publication date: 14 December 2016

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: Diamond graphs and Laakso graphs are important examples in the theory of metric embeddings. Many results for these families of graphs are similar to each other. In this connection, it is natural to ask whether one of these families admits uniformly bilipschitz embeddings into the other. The well-known fact that Laakso graphs are uniformly doubling but diamond graphs are not, immediately implies that diamond graphs do not admit uniformly bilipschitz embeddings into Laakso graphs. The main goal of this paper is to prove that Laakso graphs do not admit uniformly bilipschitz embeddings into diamond graphs.

Full work available at URL: https://arxiv.org/abs/1512.06439

Recommendations

• Distortion of embeddings of binary trees into diamond graphs
• Metric embeddings of Laakso graphs into Banach spaces
• On the geometry of the countably branching diamond graphs
• Low dimensional embeddings of doubling metrics
• DIAMOND GRAPHS AND SUPER-REFLEXIVITY

zbMATH Keywords

Lipschitz mapLaakso spacedoubling metric spacediamond graphs

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Distance in graphs (05C12)

Cites Work

• Graph theory
• Lectures on analysis on metric spaces
• Differentiability of Lipschitz maps from metric measure spaces to Banach spaces with the Radon-Nikodym property
• Embedding the diamond graph in \(L_p\) and dimension reduction in \(L_1\)
• On the impossibility of dimension reduction in l ₁
• Bilipschitz embeddings of metric spaces into space forms
• Lower bounds on the distortion of embedding finite metric spaces in graphs
• Ahlfors \(Q\)-regular spaces with arbitrary \(Q>1\) admitting weak Poincaré inequality
• Metric embeddings. Bilipschitz and coarse embeddings into Banach spaces
• On metric characterizations of some classes of Banach spaces
• A lower bound on the distortion of embedding planar metrics into Euclidean space
• Cuts, trees and \(\ell_1\)-embeddings of graphs
• DIAMOND GRAPHS AND SUPER-REFLEXIVITY
• Markov convexity and local rigidity of distorted metrics
• Metric characterizations of superreflexivity in terms of word hyperbolic groups and finite graphs
• Radon-Nikodým property and thick families of geodesics
• Metric spaces nonembeddable into Banach spaces with the Radon-Nikodým property and thick families of geodesics

Cited In (7)

• A characterization of superreflexivity through embeddings of lamplighter groups
• Embedding the diamond graph in \(L_p\) and dimension reduction in \(L_1\)
• Analysis on Laakso graphs with application to the structure of transportation cost spaces
• Some comments on Laakso graphs and sets of differences
• Metric embeddings of Laakso graphs into Banach spaces
• Lipschitz-free spaces on finite metric spaces
• A new approach to low-distortion embeddings of finite metric spaces into non-superreflexive Banach spaces

This page was built for publication: Nonexistence of embeddings with uniformly bounded distortions of Laakso graphs into diamond graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2374152)