On the $$\ell _0$$ Isoperimetric Coefficient for Measurable Sets

Abstract In this paper we prove that the $$\ell _0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>ℓ</mml:mi> <mml:mn>0</mml:mn> </mml:msub> </mml:math> isoperimetric coefficient for axis-aligned cubes, $$\psi _{\mathcal {C}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>ψ</mml:mi> <mml:mi>C</mml:mi> </mml:msub> </mml:math> , is $$\Theta (n^{-1/2})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Θ</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> and that the isoperimetric coefficient for any measurable body K , $$\psi _K$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>ψ</mml:mi> <mml:mi>K</mml:mi> </mml:msub> </mml:math> , is of order $$O(n^{-1/2})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . As a corollary we deduce that axis-aligned cubes essentially “maximize” the $$\ell _0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>ℓ</mml:mi> <mml:mn>0</mml:mn> </mml:msub> </mml:math> isoperimetric coefficient: There exists a positive constant $$q &gt; 0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>q</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mn>0</mml:mn> </mml:mrow> </mml:math> such that $$\psi _K \le q \cdot \psi _{\mathcal {C}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>ψ</mml:mi> <mml:mi>K</mml:mi> </mml:msub> <mml:mo>≤</mml:mo> <mml:mi>q</mml:mi> <mml:mo>·</mml:mo> <mml:msub> <mml:mi>ψ</mml:mi> <mml:mi>C</mml:mi> </mml:msub> </mml:mrow> </mml:math> , whenever $$\mathcal {C}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>C</mml:mi> </mml:math> 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.