Isoperimetric inequalities for faces of the cube and the grid (Q916673): Difference between revisions

By definition the grid \([p]^ N\) is \(\{0,1,...,p-1\}^ N\). The grid is a lattice in a natural sense. A down-set is a subset S of \([p]^ N\) such that for any s from S all elements smaller than s also belong to S. The weight of \(s\in [p]^ N\) is the number of coordinates taking the value p-1. The authors give estimates of down-sets containing prescribed numbers of elements with a fixed weight. The problem turns out to be equivalent to an isoperimetric problem for faces of the grid.