Edge isoperimetric theorems for integer point arrays Original Research Article

We consider subsets of the n-dimensional grid with the Manhattan metrics, (i.e., the Cartesian product of chains of lengths k1,…,kn) and study those of them which have maximal number of induced edges of the grid, and those which are separable from their complement by the least number of edges. The first problem was considered for k1=…=kn by Bollobás and Leader [1]. Here we extend their result to arbitrary k1,…,kn, and give also a simpler proof based on a new approach. For the second problem, [1] offers only an inequality. We show that our approach to the first problem also gives a solution for the second problem, if all ki = ∞. If all kiʹs are finite, we present an exact solution for n = 2.