Edge-isoperimetric inequalities in the grid.

The grid graph is the graph on [ k]={0,..., k−1} in which x=( x) is joined to y=( y) if for some i we have | x −y|=1 and x= y for all j≠ i. In this paper we give a lower bound for the number of edges between a subset of [ k] of given cardinality and its complement. The bound we obtain is essentially best possible. In particular, we show that if A⊂[ k] satisfies k/4≤| A|≤3 k/4 then there are at least k 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] of given cardinality. In particular, for r=1,..., k we show that if A⊂[ k] satisfies | A|≤ r then the subgraph of [ k] induced by A has average degree at most 2 n(1−1/ r). [ABSTRACT FROM AUTHOR]