Down-set

A down-set is a family $\mathcal{D}$ such that $A\in \mathcal{D}$ and $B\subseteq A$ imply $B\in \mathcal{D}$. It is the complement of an up-set within the same Boolean lattice.

This is the downward-closed Boolean-lattice case of upper and lower sets.

For a down-set $D$ in the Boolean lattice, every member $A$ has all its $|A|$ immediate lower neighbors in $D$. Counting an internal edge at its upper endpoint gives $e(D)={\sum }_{A\in D}|A|$. The degree identity for the edge boundary of the hypercube graph then gives the displayed formula.

For a down-set of size $m$, maximize its edge boundary by minimizing the sum of the sizes of its members. Choose all sets in the smallest ranks, followed by any needed part of the next rank; this minimizes that sum among all families and is itself a down-set. With $M_j={\sum }_{i=0}^j\left(\genfrac{}{}{0ex}{}{n}{i}\right)$, $M_{-1}=0$, and $M_{r-1}\le m\le M_r$, the exact maximum is $h(m)=nm-2[{\sum }_{j<r}j(\genfrac{}{}{0ex}{}{n}{j})+r(m-M_{r-1})]$.

For a set family $\mathcal{A}\subseteq \mathcal{P}([n])$, its downward closure is $\downarrow \mathcal{A}=\{S:\text{some }A\in \mathcal{A}\text{ has }S\subseteq A\}$. It is the smallest down-set containing $\mathcal{A}$, just as the upward closure of a set family is the smallest up-set containing it. The two closures allow Harris' inequality to control sizes of a cross-Sperner family pair.