In this paper we prove that the <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\ell _0$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>ℓ</mi> <mn>0</mn> </msub> </math></EquationSource> </InlineEquation> isoperimetric coefficient for axis-aligned cubes, <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\psi _{\mathcal {C}}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>ψ</mi> <mi mathvariant="script">C</mi> </msub> </math></EquationSource> </InlineEquation>, is <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\Theta (n^{-1/2})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Θ</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mrow> <mo>-</mo> <mn>1</mn> <mo stretchy="false">/</mo> <mn>2</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> and that the isoperimetric coefficient for any measurable body K, <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$\psi _K$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>ψ</mi> <mi>K</mi> </msub> </math></EquationSource> </InlineEquation>, is of order <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$O(n^{-1/2})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mrow> <mo>-</mo> <mn>1</mn> <mo stretchy="false">/</mo> <mn>2</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>. As a corollary we deduce that axis-aligned cubes essentially “maximize” the <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$\ell _0$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>ℓ</mi> <mn>0</mn> </msub> </math></EquationSource> </InlineEquation> isoperimetric coefficient: There exists a positive constant <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$q > 0$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>q</mi> <mo>></mo> <mn>0</mn> </mrow> </math></EquationSource> </InlineEquation> such that <InlineEquation ID="IEq10"> <EquationSource Format="TEX">$\psi _K \le q \cdot \psi _{\mathcal {C}}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>ψ</mi> <mi>K</mi> </msub> <mo>≤</mo> <mi>q</mi> <mo>·</mo> <msub> <mi>ψ</mi> <mi mathvariant="script">C</mi> </msub> </mrow> </math></EquationSource> </InlineEquation>, whenever <InlineEquation ID="IEq11"> <EquationSource Format="TEX">$\mathcal {C}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">C</mi> </math></EquationSource> </InlineEquation> 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.

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

期刊论文
出版模式：

开放获取
发表日期：

2025年6月24日

查看全文

V. Manuel Fernandez

摘要

In this paper we prove that the $\ell _0$ $ℓ_{0}$ isoperimetric coefficient for axis-aligned cubes, $\psi _{\mathcal {C}}$ $ψ_{C}$ , is $\Theta (n^{-1/2})$ $Θ (n^{- 1 / 2})$ and that the isoperimetric coefficient for any measurable body K, $\psi _K$ $ψ_{K}$ , is of order $O(n^{-1/2})$ $O (n^{- 1 / 2})$ . As a corollary we deduce that axis-aligned cubes essentially “maximize” the $\ell _0$ $ℓ_{0}$ isoperimetric coefficient: There exists a positive constant $q > 0$ $q > 0$ such that $\psi _K \le q \cdot \psi _{\mathcal {C}}$ $ψ_{K} \leq q \cdot ψ_{C}$ , whenever $\mathcal {C}$ $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.

On the \(\ell _0\) Isoperimetric Coefficient for Measurable Sets

摘要