Metric embeddings of cubes into dense subsets of cubes

Abstract

Fix $k\in \mathbb{N},0<\delta <1$. We study how large $N$ must be so that every $\delta$-dense subset $\mathcal{D}\subset \{0,1{\}}^N$ (meaning $|\mathcal{D}|\ge \delta 2^N$) contains the image of a metric embedding $f:\{0,1{\}}^k\to \mathcal{D}$. We study $3$ variants: For a $(1+\epsilon )$-bi-Lipschitz map $f$ for a fixed $\epsilon >0$, we show that $N=O({\epsilon }^{-2}\log (1/\delta )k^3)$. For an isometric map $f$ with arbitrary rescaling (i.e. undistorted), we show that $N=\log (1/\delta )e^{\Omega (k)}$. For an isometric map $f$ with bounded rescaling we show that $N=\exp [\log (1/\delta )e^{\Theta (k)}]$. Regarding the path space, we prove the density analog of a coloring theorem of Rödl--Sales. We give bounds for $(1+\epsilon )$-bi-Lipschitz embeddings of the path $[k]=\{1,...,k\}$ into dense subsets of the path $[N]=\{1,...,N\}$, improving a bound of Dumitrescu. We prove similar bounds for the binary tree space, using the tree replicas theorem of Pach--Solymosi--Tardos. As a geometric application we obtain a non-positive Alexandrov curvature counterpart to the work of Bartal--Linial--Mendel--Naor on the nonlinear Dvoretzky problem who showed that any $\mathcal{D}\subset \{0,1{\}}^N$ that embeds with bi-Lipschitz distortion $<\alpha$ into a metric space of non-negative Alexandrov curvature must be small, namely, necessarily $|\mathcal{D}|\lesssim 2^{N(1-\Omega ({\alpha }^{-2}))}$. We prove that for every $N\gtrsim {\alpha }^6\ge 1$, any $\mathcal{D}\subset \{0,1{\}}^N$ that embeds with distortion $<\alpha$ into some metric space of non-positive Alexandrov curvature must satisfy $|\mathcal{D}|\lesssim 2^{N(1-\Omega ({\alpha }^{-4}))}$ via an approach which is entirely different from that of Bartal--Linial--Mendel--Naor. We also show that nontrivial metric type and non-universality are preserved by taking finite unions of subspaces.

32 pages