Random zero sets with local growth guarantees

We prove that if $(\mathcal{M},d)$ is an $n$-point metric space that embeds quasisymmetrically into a Hilbert space, then for every $\tau >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 \tau$, the probability that both $x\in \mathcal{Z}$ and $d(y,\mathcal{Z})\ge \beta \tau \mathrm{/}\sqrt{1+\log (\mathrm{\mid }B(y,\kappa \beta \tau )\mathrm{\mid }\mathrm{/}\mathrm{\mid }B(y,\beta \tau )\mathrm{\mid })}$ is $\mathrm{\Omega }(1)$, where $\kappa >1$ is a universal constant and $\beta >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 ${\mathrm{\ell }}_1$ is $\mathrm{\Theta }(\sqrt{\log n})$, and the integrality gap of the Goemans–Linial semidefinite program for the Sparsest Cut problem on inputs of size $n$ is $\mathrm{\Theta }(\sqrt{\log n})$. Multiple further applications are given.