Nonlinear type and metric embeddings of lamplighter spaces

Abstract

We prove that for all metric spaces $X$ the following properties of the lamplighter space $\mathsf{La}(X)$ are equivalent: (1) every snowflake of $\mathsf{La}(X)$ admits a biLipschitz embedding into a finite product of $\mathbb{R}$-trees, (2) every snowflake of $\mathsf{La}(X)$ admits a biLipschitz embedding into a Hilbert space, (3) $\mathsf{La}(X)$ has finite Nagata dimension, (4) $\mathsf{La}(X)$ has Markov type 2, (5) $\mathsf{La}(X)$ has nontrivial Enflo type, (6) $\mathsf{La}(X)$ does not contain the Hamming cubes with uniform distortion. We characterize metric spaces $X$ for which $\mathsf{La}(X)$ satisfies properties (1)-(6) as those that are ``TSP-efficient" - a new condition that we introduce - which roughly means that the traveling salesman problem in $X$ can be solved as ``efficiently" as the traveling salesman problem in $\mathbb{R}$, up to a constant multiplicative factor. We also prove that if such metric spaces $X$ admit a biLipschitz embedding into ${\mathbb{R}}^n$, then $\mathsf{La}(X)$ admits a biLipschitz embedding into a finite product of $\mathbb{R}$-trees, and therefore into every nonsuperreflexive Banach space. Finally, we give a full characterization of metric spaces $X$ such that the lamplighter space $\mathsf{La}(X)$ biLipschitz embeds into a Hilbert space.

arXiv commentThis is an expanded version in comparison with the first version. A second main theorem is added and some results are reformulated