Edge-isoperimetric inequalities in the grid

The grid graph is the graph on k] ⁿ ={0,...,k–1} ⁿ in whichx=(x _i ) ₁ ⁿ is joined toy=(y _i ) ₁ ⁿ if for somei we have |x _i –y _i |=1 andx _j =y _j for allji. 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 ifAk] ⁿ satisfiesk ⁿ /4|A|3k ⁿ /4 then there are at leastk ^n–1 edges betweenA 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, forr=1,...,k we show that ifAk] ⁿ satisfies |A|r ⁿ then the subgraph of k] ⁿ induced byA has average degree at most 2n(1–1/r).Research partially supported by NSF Grant DMS-8806097