Improved ${\ell }_0$-Isoperimetry for Convex Bodies via Mass Transport

Abstract

We study ${\ell }_0$ isoperimetry for a convex body $K\subset {\mathbb{R}}^n$, $n\ge 2$. For a Borel set $S\subset K$, let ${\partial }_0^{K}S$ be the set of points in $K\setminus S$ that can be reached from $S$ by changing at most one coordinate (i.e. the ${\ell }_0$ boundary of $S$). Suppose that, for some unconditional convex body $Q\subset {\mathbb{R}}^n$, numbers $r,R>0$, and possibly different centers $x_0,y_0$, \[ x_0+rQ \subset K\subset y_0+RQ. \] Writing $s=\text{vol}(S)/\text{vol}(K)$, we prove that whenever $0<s\le 1/2$, \[ \frac{\text{vol}(\partial_0^K S)}{\text{vol}(S)} \ge \frac{cr}{nR} \min\left\{1,\frac{\log(e/s)}{n}\right\}, \] where $c>0$ is an absolute constant. Consequently, the associated ${\ell }_0$-isoperimetric coefficient is at least $cr/(n^{2}R)$. Previous direct lower bounds were only known for ${\ell }_2$ and ${\ell }_{\infty }$ regularity whereas our lower bound holds directly for any $Q$-regularity, where $Q$ is an unconditional convex body. Compared to ${\ell }_2$ and ${\ell }_{\infty }$ regularity, our lower bound result improves upon the previously best known lower bounds, for any $s$, by a factor of $n$. As an application of our result, we give improved mixing time bounds for the Coordinate Hit and Run walk (CHAR). Our proof of the lower bound is based on a modification of the method of canonical paths applied to a continuous Hamming graph over our convex body. Our construction of canonical paths can be viewed as a suitable coordinate discretization of certain mass transport maps from $S$ to $S^c$. We also give complementary upper-bounds for any $Q$-regularity, with an overall factor of $n$ gap between the two.

36 pages, 2 figures