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