Annals of Combinatorics Discrete Mathematics and Combinatorics
Edge Isoperimetry of Lattices
Abstract
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-length triangular lattice (which is isomorphic to $$\mathbb {Z}^2$$ Z 2 ) where two vertices are connected by an edge if their distance is 1 or $$\sqrt{3}$$ 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.