Edge isoperimetry of lattices

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.