Vertex Isoperimetric Inequalities for a Family of Graphs on $\mathbb{Z}^k$
Vertex Isoperimetric Inequalities for a Family of Graphs on $\mathbb{Z}^k$
We consider the family of graphs whose vertex set is $\mathbb{Z}^k$ where two vertices are connected by an edge when their $\ell_\infty$-distance is 1. We prove the optimal vertex isoperimetric inequality for this family of graphs. That is, given a positive integer $n$, we find a set $A\subset \mathbb{Z}^k$ of …