EDGE-ISOPERIMETRIC INEQUALITIES IN THE GRID

The grid graph is the graph on [k]n = {0,...,k - 1}n in which x = (x(i))1n is joined to y = (y(i))1n if for some i we have \x(i) - y(i)\ = 1 and x(j) = y(j) for all j not-equal i. In this paper we give a lower bound for the number of edges between a subset of [k]n of given cardinality and its complement. The bound we obtain is essentially best possible. In particular, we show that if A subset-of [k]n satisfies k(n)/4 less-than-or-equal-to \A\ less-than-or-equal-to 3k(n)/4 then there are at least k(n-1) edges between A and its complement. Our result is apparently the first example of an isoperimetric inequality for which the extremal sets do not form a nested family. We also give a best possible upper bound for the number of edges spanned by a subset of [k]n of given cardinality. In particular, for r = 1,...,k we show that if A subset-of [k]n satisfies \A\ less-than-or-equal-to r(n) then the subgraph of [k]n induced by A has average degree at most 2n(1 - 1/r).