Edge isoperimetry of lattices

Abstract

We present two results related to an edge isoperimetric question for Cayley graphs on the integer lattice asked by Barber and Erde (Discrete Anal Paper no. 7:16, 2018). For any (undirected) graph G, the edge boundary of a subset of vertices S is the number of edges between S and its complement in G. Barber and Erde asked whether for any Cayley graph on Zd, there is always an ordering of Zd such that for each n, the first n terms minimize the edge boundary among all subsets of size n. First, we present an example of a Cayley graph Gd on Zd (for all d≥2) for which there is no such ordering. Furthermore, we show that for all n and any optimal n-vertex subset Sn of Gd, there is no infinite sequence Sn⊂Sn+1⊂Sn+2⊂⋯ of optimal sets Si, where |Si|=i for i≥n. This is to be contrasted with the positive result in Z1 shown by Joseph Briggs and Chris Wells [arXiv:2402.14087]. Our second result is a positive example for the unit-length triangular lattice (which is isomorphic to Z2) where two vertices are connected by an edge if their distance is 1 or 3. We show that this graph has such an ordering. This is the most complicated example known to us of a two-dimensional Cayley graph for which an ordering exists.