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.