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 $$\mathbb {Z}^d$$ Z d , there is always an ordering of $$\mathbb {Z}^d$$ Z d 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 $$G_d$$ G d on $$\mathbb {Z}^d$$ Z d (for all $$d\ge 2$$ d ≥ 2 ) for which there is no such ordering. Furthermore, we show that for all n and any optimal n -vertex subset $$S_n$$ S n of $$G_d$$ G d , there is no infinite sequence $$S_n\subset S_{n+1}\subset S_{n+2}\subset \cdots $$ S n ⊂ S n + 1 ⊂ S n + 2 ⊂ ⋯ of optimal sets $$S_i$$ S i , where $$|S_i|=i$$ | S i | = i for $$i\ge n$$ i ≥ n . This is to be contrasted with the positive result in $$\mathbb {Z}^1$$ Z 1 shown by Joseph Briggs and Chris Wells [arXiv:2402.14087]. Our second result is a positive example for the unit-le