Edge Boundaries for a Family of Graphs on ${\mathbb{Z}}^n$

Abstract

We consider the family of graphs whose vertex set is ${\mathbb{Z}}^n$ where two vertices are connected by an edge when their ${\ell }_{\infty }$-distance is 1. Towards an edge isoperimetric inequality for this graph, we calculate the edge boundary of any finite set $S\subset {\mathbb{Z}}^n$. This boundary calculation leads to a desire to show that a set with optimal edge boundary has no ``gaps'' in any direction $\epsilon \in \{-1,0,1{\}}^n,\epsilon \ne 0$. We show that one can find a set with optimal edge boundary that does not have gaps in any direction $e_i$ (or $-e_i$) where $e_i$ is the standard basis vector.

arXiv comment13 pages, 11 figures