Past exam of the mathematics course of the University of Cambridge / 2018 / iii / Paper 109 / 1

Choose a Uniformly random maximal chain in a Boolean lattice by taking a uniformly random permutation of $X$ and successively adjoining its elements. A fixed $r$-element set occurs on this maximal chain in a Boolean lattice with probability $r!(n-r)!/n!={\left(\genfrac{}{}{0ex}{}{n}{r}\right)}^{-1}$. Because an antichain meets every such chain in a partially ordered set at most once, linearity of expectation gives the LYM inequality:Here $L(\mathcal{A})$ is the Lubell mass.

For equality in the LYM inequality, the integer $|\mathcal{A}\cap \mathcal{C}|\le 1$ must equal one for every maximal chain in a Boolean lattice, since every chain has positive probability. Choose $A\in \mathcal{A}$ of rank $r$. If $0<r<n$, take $x\in A$ and $y\notin A$, and choose a permutation with its first $r$ elements equal to $A$, its $r$th element $x$, and its next element $y$. Interchanging those two adjacent elements changes precisely the rank-$r$ member of the corresponding maximal chain in a Boolean lattice, replacing $A$ by $A^{\prime }=A\setminus \{x\}\cup \{y\}$. All other members are unchanged and none belongs to the antichain. The new chain must still meet $\mathcal{A}$, so $A^{\prime }\in \mathcal{A}$.

Successive exchanges connect all $r$-element subsets: exchange an element outside a desired target for an element missing from it, decreasing the number of differences each time. Thus $\mathcal{A}$ contains the whole rank-$r$ level. Every set of another rank is comparable with some set in that level, so the antichain contains nothing else. If $r=0$ or $r=n$, its sole possible member is already the whole corresponding level. Conversely, every full level meets every maximal chain in a Boolean lattice exactly once. Hence

A k-Sperner family meets every maximal chain in a Boolean lattice in at most $k$ members. The random-chain calculation in part (a) therefore gives the generalized LYM inequality $L(\mathcal{A})\le k$. Define the proportion of rank $i$ that is present byThen ${\sum }_i{x}_i=L(\mathcal{A})\le k$ and $w(\mathcal{A})={\sum }_{i}u(i)x_i$. This reduces the weighted theorem for k-Sperner families to allocating at most $k$ units of mass among ranks, each of capacity one.

To handle ties explicitly, let $t>0$ be the $k$th largest value among the $u(i)$, let $H=\{i:u(i)>t\}$, and put $h=|H|<k$. ThenThe last expression is exactly the sum of the $k$ largest rank weights, with multiplicity. Writing those values in descending order as $u_{(1)},\dots ,u_{(n+1)}$, the answer is

Choose $k$ distinct ranks whose $u(i)$ values are the $k$ largest, resolving any tie arbitrarily, and take the union of their full levels. Along a strict chain in a partially ordered set, cardinality strictly increases, so this set family is a k-Sperner family. Its weight is the sum of the selected rank weights because a full level of rank $i$ has $\left(\genfrac{}{}{0ex}{}{n}{i}\right)$ members. Thus the bound in the weighted theorem for k-Sperner families is always attained:

First we need all equality cases, rather than just the examples from part (c). The threshold estimate in part (b), with $t>0$, shows that any maximum-weight k-Sperner family has Lubell mass exactly $k$.

For each $A\in \mathcal{A}$, let $\ell (A)$ be the largest number of members in a strict chain in a partially ordered set within $\mathcal{A}$ ending at $A$. Its values lie in $\{1,\dots ,k\}$. If $A⊊B$ then $\ell (B)\ge \ell (A)+1$, so each height class ${\mathcal{A}}_j=\{A:\ell (A)=j\}$ is an antichain. Its Lubell mass is at most one by the LYM inequality, andConsequently every height class has Lubell mass one. By equality in the LYM inequality, each is a full rank level. Since the classes are disjoint, the maximizing family is a union of exactly $k$ distinct full levels.

Let $t$ again be the $k$th largest $u(i)$, let $h$ ranks have $u(i)>t$, and let $s$ ranks have $u(i)=t$. Equality in the threshold estimate requires all $h$ higher-weight levels, no lower-weight levels, and any $k-h$ of the $s$ tied levels. Thus the number of maximizing weighted k-Sperner families isConversely, every such $h,s$ is realizable. Assign $u(i)=2$ on $h$ chosen ranks, $u(i)=1$ on $s$ further ranks, and $u(i)=1/2$ on all remaining ranks, then set $w(i)=u(i)/\left(\genfrac{}{}{0ex}{}{n}{i}\right)$. These weights are positive and have exactly the stated tie pattern.

Putting $j=k-h$ gives a concise classification of the possible integers:Repeated values in this set are counted only once. The possible counts need not form an interval: for example, when $n=5,k=2$ they are $1,2,3,4,5,6,10,15$.