Stochastic approximation of lamplighter metrics

DOI10.1112/BLMS.12657MaRDI QIDQ6048880zbMATH OpenOpenAlexFDO

Authors Florent Baudier, Pavlos Motakis, Th. Schlumprecht, A. Zsák

Publication date 15 September 2023

Published in Bulletin of the London Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

$L_1$-distortionlamplighter grouplamplighter metricLipschitz free spaces

Mathematics Subject Classification ID

Distance in graphs (05C12) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Embeddings of discrete metric spaces into Banach spaces; applications in topology and computer science (46B85) Lipschitz and coarse geometry of metric spaces (51F30)

Abstract: We observe that embeddings into random metrics can be fruitfully used to study the $L_1$-embeddability of lamplighter graphs or groups, and more generally lamplighter metric spaces. Once this connection has been established, several new upper bound estimates on the $L_1$-distortion of lamplighter metrics follow from known related estimates about stochastic embeddings into dominating tree-metrics. For instance, every lamplighter metric on a $n$-point metric space embeds bi-Lipschitzly into $L_1$ with distortion $O(logn)$. In particular, for every finite group $G$ the lamplighter group $H=mathbb{Z}_{2}wrG$ bi-Lipschitzly embeds into $L_1$ with distortion $O(loglog|H|)$. In the case where the ground space in the lamplighter construction is a graph with some topological restrictions, better distortion estimates can be achieved. Finally, we discuss how a coarse embedding into $L_1$ of the lamplighter group over the $d$-dimensional infinite lattice $mathbb{Z}^d$ can be constructed from bi-Lipschitz embeddings of the lamplighter graphs over finite $d$-dimensional grids, and we include a remark on Lipschitz free spaces over finite metric spaces.

Recommendations

• The Euclidean distortion of the lamplighter group.
• On the bi-Lipschitz geometry of lamplighter graphs
• A characterization of superreflexivity through embeddings of lamplighter groups
• \(L_{1}\) embeddings of the Heisenberg group and fast estimation of graph isoperimetry

Cites work

• \(L^{p}\)-distortion and \(p\)-spectral gap of finite graphs
• \(L_p\) compression, traveling salesmen, and stable walks.
• \(L_{1}\) embeddings of the Heisenberg group and fast estimation of graph isoperimetry
• A characterization of superreflexivity through embeddings of lamplighter groups
• A Graph-Theoretic Game and Its Application to the k-Server Problem
• A tight bound on approximating arbitrary metrics by tree metrics
• Amenable groups with very poor compression into Lebesgue spaces
• Approximate nearest neighbor search in high dimensions
• Approximation algorithms for classification problems with pairwise relationships, metric labeling and Markov random fields
• Asymptotic isoperimetry on groups and uniform embeddings into Banach spaces
• Book review of: M. I. Ostrovskii, Metric embeddings: Bilipschitz and coarse embedddings into Banach spaces
• Characterization of metric spaces whose free space is isometric to \(\ell_1\)
• COARSE EMBEDDINGS INTO A HILBERT SPACE, HAAGERUP PROPERTY AND POINCARÉ INEQUALITIES
• Compression bounds for wreath products.
• Compression functions of uniform embeddings of groups into Hilbert and Banach spaces
• Cuts, trees and \(\ell_1\)-embeddings of graphs
• DIAMOND GRAPHS AND SUPER-REFLEXIVITY
• Embedding k-Outerplanar Graphs into l1
• Embedding Subspaces of L 1 into l N 1
• Embeddings of Discrete Groups and the Speed of Random Walks
• EXACTNESS AND UNIFORM EMBEDDABILITY OF DISCRETE GROUPS
• Free spaces over some proper metric spaces
• Graph minors. I. Excluding a forest
• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• scientific article; zbMATH DE number 1775395 (Why is no real title available?)
• scientific article; zbMATH DE number 1775400 (Why is no real title available?)
• Isometric group actions on Hilbert spaces: growth of cocycles
• Lamplighters, Diestel–Leader Graphs, Random Walks, and Harmonic Functions
• Large scale geometry
• Lipschitz algebras
• Lipschitz-free Banach spaces
• Lipschitz-free spaces on finite metric spaces
• Lipschitz-free spaces over ultrametric spaces
• Lower bounds on the distortion of embedding finite metric spaces in graphs
• Metric cotype
• Metric embeddings. Bilipschitz and coarse embeddings into Banach spaces
• Nonembeddability theorems via Fourier analysis
• On approximating planar metrics by tree metrics.
• On the \(L^p\)-distortion of finite quotients of amenable groups
• On the Banach-Mazur distance to cross-polytope
• On the bi-Lipschitz geometry of lamplighter graphs
• On the impossibility of dimension reduction in l ₁
• Pathwidth, trees, and random embeddings
• Planar Earthmover Is Not in L₁
• Proper actions of lamplighter groups associated with free groups
• Proper actions of wreath products and generalizations.
• Quantitative geometry
• Quantitative property A, Poincaré inequalities, L^p-compression and L^p-distortion for metric measure spaces
• Random walks on the lamplighter group
• Rectifiable sets and the traveling salesman problem
• RESTRICTED INVERTIBILITY AND THE BANACH–MAZUR DISTANCE TO THE CUBE
• Sharp quantitative nonembeddability of the Heisenberg group into superreflexive Banach spaces
• Similarity estimation techniques from rounding algorithms
• Steiner points in tree metrics don't (really) help
• The dimension of almost spherical sections of convex bodies
• The Euclidean distortion of the lamplighter group.
• The geometry of graphs and some of its algorithmic applications
• The metrical interpretation of superreflexivity in Banach spaces
• The wreath product of $\mathbb {Z}$ with $\mathbb {Z}$ has Hilbert compression exponent $\frac {2}{3}$
• Trees and Markov convexity
• Un théorème sur les opérateurs linéaires entre espaces de Banach qui se factorisent par un espace de Hilbert
• Wreath products with the integers, proper actions and Hilbert space compression.

Cited in

(3)

• Wasserstein distance and metric trees
• Stochastic embeddings of graphs into trees
• Hyperbolic metric spaces and stochastic embeddings

This page was built for publication: Stochastic approximation of lamplighter metrics

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