Isoperimetry in integer lattices

- School of Mathematics, University of Bristol
- More about Ben Barber

- Fachbereich Mathematik, Universität Hamburg

*Discrete Analysis*, April. https://doi.org/10.19086/da.3555.

### Editorial introduction

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 ℓ1-distance 1, was solved by Bollobás and Leader in the 1990s, who showed that the optimal shapes consist of ℓ∞-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 ℓ∞-distance instead.

In the present paper the authors solve the edge-isoperimetric problem asymptotically for every Cayley graph on G=Zd, 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 Zd with the ℓ∞-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 Γ(G,U) has vertex set G and edge set {(g,g+u):g∈G,u∈U}. This construction includes both the ℓ1 and the ℓ∞ graph defined above, by considering the generating sets U1={(±1,0,…,0),…,(0,…,0,±1)} and U∞={−1,0,1}d∖{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={u1,u2,…,uk} 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,u1}+{0,u2}+⋯+{0,uk} with Zd. For example, when d=2, then the zonotope for the ℓ∞ 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.