Random zero sets with local growth guarantees

Abstract

We prove that if $(\mathcal{M},d)$ is an $n$-point metric space that embeds quasisymmetrically into a Hilbert space, then for every $\ddot{I}„>0$ there is a random subset $\mathcal{Z}$ of $\mathcal{M}$ such that for any pair of points $x,y\in \mathcal{M}$ with $d(x,y)\ge \ddot{I}„$, the probability that both $x\in \mathcal{Z}$ and $d(y,\mathcal{Z})\ge {\hat{I}}^2\ddot{I}„/\sqrt{1+\log (|B(y,\hat{I}º{\hat{I}}^2\ddot{I}„)|/|B(y,{\hat{I}}^2\ddot{I}„)|)}$ is $\hat{I}\text{c◯}(1)$, where $\hat{I}º>1$ is a universal constant and ${\hat{I}}^2>0$ depends only on the modulus of the quasisymmetric embedding. The proof relies on a refinement of the Arora--Rao--Vazirani rounding technique. Among the applications of this result is that the largest possible Euclidean distortion of an $n$-point subset of ${\ell }_1$ is $\hat{I}˜(\sqrt{\log n})$, and the integrality gap of the Goemans--Linial semidefinite program for the Sparsest Cut problem on inputs of size $n$ is $\hat{I}˜(\sqrt{\log n})$. Multiple further applications are given.

added Section 1.1 (informal overview), the rest of the material is the same