Edge-Isoperimetric Inequalities in Chamber Graphs of Hyperplane Arrangements

Abstract

We study edge-isoperimetric inequalities in chamber graphs of affine hyperplane arrangements. Our approach is topological: to a set of chambers we associate its thickening in Euclidean space and estimate its edge boundary through the induced stratification by intersections of arrangement hyperplanes. This yields general lower bounds for a broad class of sets. We show that a convex set of chambers of size ${\sum }_{i=0}^d\left(\genfrac{}{}{0ex}{}{k}{i}\right)$, with $k\ge d-1$, has edge boundary at least ${\sum }_{i=0}^{d-1}\left(\genfrac{}{}{0ex}{}{k}{i}\right)$, and we conjecture that convex sets minimize the edge boundary among all chamber sets of a fixed size. We verify this conjecture in dimension $2$. Our main result is a three-dimensional asymptotic inequality for arbitrary subsets of chambers: for arrangements in general position, every set $S$ occupying at most a fixed proportion of the chambers satisfies $|\partial S|=\Omega (|S{|}^{2/3})$. As a consequence, for an arrangement of $n$ hyperplanes in general position in ${\mathbb{R}}^3$, the lazy simple random walk on the chamber graph has $\epsilon$-mixing time $O(n^2\log (n/\epsilon ))$.