On the ${\ell }_0$ Isoperimetric Coefficient of Measurable Sets

Abstract

In this paper we prove that the ${\ell }_0$ isoperimetric coefficient for any axis-aligned cubes, ${\psi }_{\mathcal{C}}$, is $\Theta (n^{-1/2})$ and that the isoperimetric coefficient for any measurable body $K$, ${\psi }_K$, is of order $O(n^{-1/2})$. As a corollary we deduce that axis-aligned cubes essentially "maximize" the ${\ell }_0$ isoperimetric coefficient: There exists a positive constant $q>0$ such that ${\psi }_K\le q\cdot {\psi }_{\mathcal{C}}$, whenever $\mathcal{C}$ is an axis-aligned cube and $K$ is any measurable set. Lastly, we give immediate applications of our results to the mixing time of Coordinate-Hit-and-Run for sampling points uniformly from convex bodies.

Revised and accepted to Discrete and Computational Geometry