ISOPERIMETRIC-INEQUALITIES FOR FACES OF THE CUBE AND THE GRID

A face of the cube ℘(N) = {0,1}N is a subset determined by fixing the values of some coordinates and allowing the remainder free rein. For instance, the edges of the cube are faces of dimension 1. In Section 2 of this paper we prove a best possible upper bound for the number of i-faces of ℘(N) contained in any subset of ℘(N). In particular, we show that initial segments in the binary ordering the ordering on ℘(N) induced by the map A↦ Σi∈ A 2i: ℘(N)→ ℕ—contain the greatest possible number of i-faces for any i ⩾0. In Section 3 the inequality is extended to apply to the grid [p]N for p ⩾ 2, and to give a bound on the number of i-dimensional faces enclosed by a collection of j-dimensional faces, for i ⩾j. Finally, in Section 4, we apply the face isoperimetric result to the problem which originally motivated its study. We prove a Kruskal-Katona type result for down-sets in the grid. © 1990, Academic Press Limited. All rights reserved.