Isoperimetry in integer lattices

Isoperimetry in integer lattices, Discrete Analysis 2018:7, 16 pp.

The isoperimetric problem, already known to the ancient Greeks, concerns the minimisation of the size of a boundary of a set under a volume constraint. The problem has been studied in many contexts, with a wide range of applications. The present paper focuses on the discrete setting of graphs, where the boundary of a subset of vertices can be defined with reference to either vertices or edges. Specifically, the so-called edge-isoperimetric problem for a graph $G$ is to determine, for each $n$, the minimum number of edges leaving any set $S$ of $n$ vertices. The vertex isoperimetric problem asks for the minimum number of vertices that can be reached from $S$ by following these edges.

For a general graph $G$ this problem is known to be NP-hard, but exact solutions are known for some special classes of graphs. One example is the $d$-dimensional hypercube, which is the graph on vertex set $\{0,1\}^d$ with edges between those binary strings of length $d$ that differ in exactly one coordinate. The edge-isoperimetric problem for this graph was solved by Harper, Lindsey, Bernstein, and Hart, and the extremal sets include $k$-dimensional subcubes obtained by fixing $d-k$ of the coordinates.

The edge-isoperimetric problem for the $d$-dimensional integer lattice whose edges connect pairs of vertices at $\ell_1$-distance 1, was solved by Bollobás and Leader in the 1990s, who showed that the optimal shapes consist of $\ell_\infty$-balls. More recently, Radcliffe and Veomett solved the vertex-isoperimetric problem for the $d$-dimensional integer lattice on which edges are defined with respect to the $\ell_\infty$-distance instead.

In the present paper the authors solve the edge-isoperimetric problem asymptotically for every Cayley graph on $G=\mathbb{Z}^d$, and determine the near-optimal shapes in terms of the generating set used to construct the Cayley graph. In particular, this solves the edge-isoperimetric problem on $\mathbb{Z}^d$ with the $\ell_\infty$-distance.

We now describe the results in more detail. Given any generating set $U$ of $G$ that does not contain the identity, the Cayley graph $\Gamma(G,U)$ has vertex set $G$ and edge set $\{(g,g+u): g\in G, u\in U\}$. This construction includes both the $\ell_1$ and the $\ell_\infty$ graph defined above, by considering the generating sets $U_1=\{(\pm 1, 0,\dots,0),\dots,(0,\dots,0,\pm 1)\}$ and $U_\infty=\{-1,0,1\}^d\setminus\{0,0,0\}$, respectively.

The near-optimal shapes obtained by the authors are so-called zonotopes, generated by line segments corresponding to the generators of the Cayley graph. More precisely, if $U=\{u_1,u_2,\dots,u_k\}$ is a set of non-zero generators of $G$, then the near-optimal shapes are the intersections of scaled copies of the convex hull of the sum set $\{0,u_1\}+\{0,u_2\}+\dots+\{0,u_k\}$ with $\mathbb{Z}^d$. For example, when $d=2$, then the zonotope for the $\ell_\infty$ problem is an octagon obtained by cutting the corners off a square through points one third of the way along each side.

In contrast to the aforementioned edge-isoperimetry results, which were solved exactly using compression methods, the approach in this paper is an approximate one. It follows an idea of Ruzsa, who solved the vertex-isoperimetry problem in general Cayley graphs on the integer lattice by approximating the discrete problem with a continuous one. While the continuous analogue in the present paper is a natural one, it is not clear that it is indeed a good approximation to the original problem, and it is here that the main combinatorial contribution of the paper lies. It concludes with several open problems and directions for further work.