Annals of Combinatorics Discrete Mathematics and Combinatorics

Edge Isoperimetry of Lattices

Cameron Strachan, Konrad Swanepoel
Springer Nature · 2026-01-05 · DOI 10.1007/s00026-025-00801-x

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.

Read at publisher →