Boolean lattice ($\mathcal{P}([n])$)

The Boolean lattice is the power set of a finite set ordered by inclusion. Its rank-$h$ level consists of all $h$-element subsets.

A family in the Boolean lattice whose pairwise Hamming distances are at most $d<n$ has size at most $D(n,d)$. Downward compression followed by elementary set shifts preserves the distance bound. In the resulting down-set, the section containing the last coordinate has diameter at most $d-2$: two members leave a coordinate free, and shifting the last coordinate to it creates a pair with two additional disagreements. This gives the recurrence $D(n,d)=D(n-1,d)+D(n-1,d-2)$. The boundary case $d=n-1$ follows by pairing complementary sets. Hamming balls attain the even case; the union of two radius-$q$ balls with adjacent centers attains the odd case.

If $n\ge 2d+1$ and the field characteristic is zero or greater than $d+1$, the matrix recording inclusion of $d$-sets in $(d+1)$-sets has full row rank. Subtracting equations on sets differing in one coordinate reduces the kernel problem to degree $d-1$ on $n-2$ coordinates. Mathematical induction then makes all coefficients equal, and the factor $d+1$ forces them to vanish. This gives the auxiliary-polynomial independence used in the uniform Frankl-Wilson theorem.

An up-set is a family $\mathcal{U}$ such that $A\in \mathcal{U}$ and $A\subseteq B$ imply $B\in \mathcal{U}$.

An up-set is upward closed under inclusion: if $A$ belongs and $A\subseteq B$, then $B$ belongs. This is the Boolean-lattice case of upper and lower sets.

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.

An antichain is a family of sets no one of which contains another.

A maximal chain in $\mathcal{P}([n])$ contains one set of every cardinality from zero to $n$, with each set obtained from the preceding one by adding a single element.

A uniformly random maximal chain is obtained from a uniformly random ordering of the ground set by taking its successive initial segments. A fixed $h$-element set occurs with probability ${\left(\genfrac{}{}{0ex}{}{n}{h}\right)}^{-1}$.

If $\mathcal{A}$ is an antichain in $\mathcal{P}([n])$ and ${\mathcal{A}}_h$ is its rank-$h$ part, thenThe left side is the expected number of members of $\mathcal{A}$ on a Uniformly random maximal chain in a Boolean lattice.

An antichain in the Boolean lattice has Lubell mass one if and only if it is a full rank level. Equality means every maximal chain in a Boolean lattice meets the family exactly once. Swapping two adjacent entries in the defining permutation then forces the family to contain every set obtained from one member by exchanging an included and an excluded element, hence every set of that rank.

The Lubell mass of a set family $\mathcal{A}\subseteq \mathcal{P}([n])$ isIt is the expected value of the number of members of $\mathcal{A}$ on a Uniformly random maximal chain in a Boolean lattice.

For $\mathcal{A}\subseteq [n{]}^{(r)}$, the local LYM inequality saysIt follows by counting pairs $(B,A)$ with $B\subset A$, $|B|=r-1$, and $A\in \mathcal{A}$.

The bipartite inclusion graph between consecutive nonempty ranks of the Boolean lattice is connected. Two rank-$r$ sets differing by one exchanged element share their rank-$(r+1)$ union as a neighbour; successive exchanges connect any two rank-$r$ sets. Every upper vertex has a lower neighbour. For the two middle ranks of an odd-dimensional Boolean lattice the graph is regular, so equality in the Local LYM inequality for a nonempty upper family forces the whole upper rank: equality admits no edges from its lower shadow to the remaining upper vertices.

Repeatedly applying the Local LYM inequality to upper shadows givesfor $\mathcal{A}\subseteq [n{]}^{(r)}$ and $0\le s\le n-r$. The analogous statement for iterated lower shadows follows directly from the stated lower-shadow form.

Every antichain in $\mathcal{P}([n])$ has at most $\left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$ members. Equality is attained only by a full middle level, with either middle level possible when $n$ is odd.

For vectors of norm at least one, the number of signed sums in an open unit ball is at most the central binomial coefficient. In one dimension this follows from the antichain bound. In Euclidean spaces a separated block decomposition for vector subset sums supplies the same bound without assuming all vectors have positive projection in one common direction. Signed sums are counted with multiplicity, by their sign choices.

For real coefficients of absolute value at least one, an open interval of length four contains at most the sum of the two largest binomial coefficients of signed sums. The corresponding subset family has no three-element inclusion chain. Its Lubell mass is therefore at most two, giving the bound by allocating mass to the two largest levels. Unit coefficients attain it at a center midway between the two chosen sum levels.

For Euclidean vectors $x_i$ of length at least one, their labeled subset sums can be partitioned into pairwise distance-at-least-one blocks, with $\left(\genfrac{}{}{0ex}{}{n}{r}\right)-\left(\genfrac{}{}{0ex}{}{n}{r-1}\right)$ blocks of size $n-2r+1$. To extend a separated block by a vector $x$, choose its member $y$ minimizing inner product with $x$. The translated block together with $y$ remains separated, since $(z+x-y)\cdot x\ge \Vert x{\Vert }^2$. The untransformed block with $y$ removed remains separated too. Block sizes change from $\ell$ to $\ell +1,\ell -1$, the same recurrence as a symmetric chain decomposition of a Boolean lattice. There are exactly $\left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$ nonempty blocks.

The maximum antichains in the Boolean lattice are exactly its full middle levels. For even $n$ there is one such level, and for odd $n$ either middle level works. The LYM inequality first confines a maximum antichain to those levels; connectedness of the regular inclusion bipartite graph rules out a mixture of the two odd middle levels.

A $k$-Sperner family contains no inclusion chain of length $k+1$. Every maximal chain in a Boolean lattice therefore meets it in at most $k$ members, so its Lubell mass is at most $k$.

For positive weights $w(i)$ depending only on rank, put $u_i=\left(\genfrac{}{}{0ex}{}{n}{i}\right)w(i)$. The largest weight of a k-Sperner family in $\mathcal{P}([n])$ is the sum of the $k$ largest $u_i$. Every maximizing family is a union of $k$ full rank levels. To see the equality assertion, its Lubell mass must be $k$; decomposing it into $k$ antichains by chain height and using equality in the LYM inequality forces each part to be a full level.

If $t$ is the $k$th largest rank weight $u_i$, exactly $h$ levels have weight greater than $t$, and exactly $s$ have weight $t$, then there are $\left(\genfrac{}{}{0ex}{}{s}{k-h}\right)$ maximizing families. For fixed $n,k$, the possible counts are exactly $\left(\genfrac{}{}{0ex}{}{s}{j}\right)$ with $1\le j\le k$ and $j\le s\le n+1-k+j$.

Among $k$-Sperner subfamilies of $\mathcal{P}([n])$, the maximum cardinality is the sum of the $k$ largest binomial coefficients $\left(\genfrac{}{}{0ex}{}{n}{j}\right)$. The union of the corresponding levels attains the bound. For the upper bound, the Lubell mass is at most $k$, and assigning its available mass to the levels with largest binomial coefficients maximizes cardinality.

If set families $\mathcal{A},\mathcal{B}\subseteq \mathcal{P}([n])$ are cross-incomparable, meaning no member of either contains a member of the other, thenThe proof applies the Harris-Kleitman inequality to the upward closures generated by the two families.

Choose disjoint subsets $K_1,K_2\subseteq [n]$ of size $k\ge 1$ with $2k\le n$. Let $\mathcal{A}$ consist of subsets containing all of $K_1$ and none of $K_2$; let $\mathcal{B}$ consist of subsets omitting at least one point of $K_1$ and containing at least one point of $K_2$. These form a cross-Sperner family pair, with sizes $2^{n-2k}$ and $(2^k-1{)}^2{2}^{n-2k}$. Their square roots sum to $2^{n/2}$, proving sharpness of the Cross-Sperner inequality. The free coordinates outside the two blocks account for the factor $2^{n-2k}$.