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

DOI10.1016/J.DISC.2016.08.003MaRDI QIDQ2374152zbMATH OpenOpenAlexFDO

Authors Sofiya Ostrovska, Mikhail Ostrovskii

Publication date 14 December 2016

Published in Discrete Mathematics (Search for Journal in Brave)

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

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)

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.

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

Cites work

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

Cited in

(7)

• Some comments on Laakso graphs and sets of differences
• Analysis on Laakso graphs with application to the structure of transportation cost spaces
• A characterization of superreflexivity through embeddings of lamplighter groups
• Lipschitz-free spaces on finite metric spaces
• Metric embeddings of Laakso graphs into Banach spaces
• Embedding the diamond graph in \(L_p\) and dimension reduction in \(L_1\)
• 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)