Fix $k \in \mathbb{ N}$ and $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}| \geq \delta 2^N$) contains the image of a metric embedding $f: \{ 0,1\}^k \to \mathcal{ D}$. We study three variants. For a $(1+\varepsilon)$-bi-Lipschitz map $f$ with fixed $\varepsilon > 0$, we show $N = O(\varepsilon^{ -2} \log(1/\delta) k^3)$. For an isometric map with arbitrary rescaling (undistorted), we show $N = \log(1/\delta) e^{ \Omega(k)}$ and conjecture $N = \log(1/\delta) e^{ O(k)}$. For an isometric map with bounded rescaling we show $N = \exp[\log(1/\delta) e^{ \Theta(k)}]$. As a geometric application, we obtain a nonpositive Alexandrov curvature counterpart to the work of Bartal-Linial-Mendel-Naor on the nonlinear Dvoretzky problem. It is known that any subset of $\{ 0,1\}^N$ embedding with bi-Lipschitz distortion $< \alpha$ into a metric space of nonnegative Alexandrov curvature must satisfy $|\mathcal{ D}| \lesssim 2^{ N(1-\Omega(\alpha^{ -2}))}$. Work of Gromov and Kondo shows that this approach does not extend to CAT(0) targets. We prove that for every $N \gtrsim \alpha^6 \geq 1$, any $\mathcal{ D} \subset \{ 0,1\}^N$ embedding with distortion $< \alpha$ into a CAT(0) space must satisfy $|\mathcal{ D}| \lesssim 2^{ N(1-\Omega(\alpha^{ -4}))}$, via a completely different approach. Similar results hold for targets of nontrivial Enflo type. Finally, we prove the density analogue of a coloring theorem of Rodl-Sales: we give bounds for $(1+\varepsilon)$-bi-Lipschitz embeddings of the path $\{ 1,\ldots,k\}$ into dense subsets of $\{ 1,\ldots,N\}$ (improving a bound of Dumitrescu), and prove similar bounds for binary tree metrics.

Categories: math.CO math.MG

Metric embeddings of cubes into dense subsets of cubes