Improved ℓ0-Isoperimetry for Convex Bodies via Mass Transport
Abstract
We study ℓ0 isoperimetry for a convex body K⊂ ℝn, n≥2. For a Borel set S⊂ K, let ∂0K S be the set of points in K ∖ S that can be reached from S by changing at most one coordinate (i.e. the ℓ0 boundary of S). Suppose that, for some unconditional convex body Q ⊂ ℝn, numbers r,R>0, and possibly different centers x0,y0, x0+rQ ⊂ K⊂ y0+RQ. Writing s=vol(S)/vol(K), we prove that whenever 0<s ≤ 1/2, (vol(∂0K S))/vol(S) ≥ cr/nR min{1,log(e/s)/n}, where c > 0 is an absolute constant. Consequently, the associated ℓ0-isoperimetric coefficient is at least cr/(n2R). Previous direct lower bounds were only known for ℓ2 and ℓ∞ regularity whereas our lower bound holds directly for any Q-regularity, where Q is an unconditional convex body. Compared to ℓ2 and ℓ∞ 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 Sc. We also give complementary upper-bounds for any Q-regularity, with an overall factor of n gap between the two.
Related
- The Petty Conjecture for Convex Bodies of Revolution
- Riemannian convex bodies with a geodesic segment on the boundary
- Continuity and monotonicity of weighted perimeters of convex bodies
- Comment on "The polarization hierarchy for polynomial optimization over convex bodies, with applications to nonnegative matrix rank"
- A Nearly Quadratic Lower Bound for Linear Optimization over Convex Bodies in the Membership Oracle Model
BibTeX
@misc{fernandez2026improved,
title = {{Improved $\ell_0$-Isoperimetry for Convex Bodies via Mass Transport}},
author = {Manuel Fernandez V},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.27854},
eprint = {2608.27854},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.27854},
}
RIS
TY - UNPB
TI - Improved ℓ_0-Isoperimetry for Convex Bodies via Mass Transport
AU - Manuel Fernandez V
PY - 2026
DA - 2026/08/28
PB - arXiv
DO - 10.48550/arxiv.2608.27854
UR - https://arxiv.org/abs/2608.27854
AB - We study ℓ_0 isoperimetry for a convex body K⊂ ℝ^n, n≥2. For a Borel set S⊂ K, let ∂_0^K S be the set of points in K ∖ S that can be reached from S by changing at most one coordinate (i.e. the ℓ_0 boundary of S). Suppose that, for some unconditional convex body Q ⊂ ℝ^n, numbers r,R>0, and possibly different centers x_0,y_0, x_0+rQ ⊂ K⊂ y_0+RQ. Writing s=vol(S)/vol(K), we prove that whenever 0<s ≤ 1/2, (vol(∂_0^K S))/vol(S) ≥ cr/nR min{1,log(e/s)/n}, where c > 0 is an absolute constant. Consequently, the associated ℓ_0-isoperimetric coefficient is at least cr/(n^2R). Previous direct lower bounds were only known for ℓ_2 and ℓ_∞ regularity whereas our lower bound holds directly for any Q-regularity, where Q is an unconditional convex body. Compared to ℓ_2 and ℓ_∞ 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.
ER -