Antichain

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}$.