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

For a uniform set family $\mathcal{A}\subseteq [n{]}^{(r)}$, the Local LYM inequality isTo prove it, count the incident pairs $(B,A)$ with $B\in \partial \mathcal{A}$, $A\in \mathcal{A}$, and $B\subset A$. Every $A$ contributes exactly $r$ pairs, whereas every $B$ belongs to at most $n-r+1$ members of $[n{]}^{(r)}$. Thereforewhich is the displayed inequality after using the binomial coefficient identity $r\left(\genfrac{}{}{0ex}{}{n}{r}\right)=(n-r+1)\left(\genfrac{}{}{0ex}{}{n}{r-1}\right)$.

The LYM inequality says that every antichain $\mathcal{A}\subseteq \mathcal{P}([n])$ satisfiesFor the proof from the local inequality, take the lowest occupied level below the middle and replace that level by its upper shadow. The result remains an antichain: any new containment involving a set in the upper shadow would already give a containment involving the member of $\mathcal{A}$ immediately below it. The dual form of the Local LYM inequality says that this replacement cannot decrease the Lubell mass. Repeating upward below the middle, and similarly replacing high levels by their lower shadows, eventually puts the whole family in one middle level. Its final Lubell mass is at most one, so the original mass is also at most one.

For the maximal chain in a Boolean lattice proof, choose a Uniformly random maximal chain in a Boolean lattice. An $h$-element set lies on it with probability $1/\left(\genfrac{}{}{0ex}{}{n}{h}\right)$. Because an antichain meets each chain at most once, the expected value of the number of its members on the chain is at most one. By linearity of expectation, that expected value is precisely the displayed sum.

The Sperner theorem follows because $\left(\genfrac{}{}{0ex}{}{n}{|A|}\right)\le \left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$ for every $A$. If equality holds in the resulting cardinality bound, every member lies on a largest level. For even $n$ this is the unique middle level. For odd $n$, the two middle levels have equal size; the regular connected inclusion graph between them and equality in Local LYM inequality force a chosen portion of the lower level to be either empty or the whole level. Hence the maximum antichains are exactly the complete middle level, with either middle level allowed when $n$ is odd.

The hypothesis says exactly that $\mathcal{A}$ is a k-Sperner family with $k=2$: it contains no three members forming a strict inclusion chain. Every maximal chain in a Boolean lattice consequently contains at most two members of $\mathcal{A}$, so the same random-chain argument gives $\lambda (\mathcal{A})\le 2$. For a fixed amount of Lubell mass, cardinality is maximized by using the levels with the two largest binomial coefficients. The Erdős theorem on k-Sperner families therefore givesThe bound is attained by taking the union of two levels having those sizes.

Let $\mathcal{A}\subseteq [n{]}^{(r)}$ be an intersecting family, with $n\ge 2r$. By the Iterated local LYM inequality, its upper shadow in level $n-r$ satisfiesThe family of complements ${\mathcal{A}}^c=\{[n]\setminus A:A\in \mathcal{A}\}$ also lies in level $n-r$ and has cardinality $|\mathcal{A}|$. It is disjoint from the upper shadow: if $A\subseteq [n]\setminus B$ for $A,B\in \mathcal{A}$, then $A\cap B=\varnothing$, contradicting intersection. Both families fit inside the $(n-r)$th level, soThus replacing the Kruskal-Katona theorem by Local LYM gives onlyThis agrees with the Erdős-Ko-Rado theorem when $n=2r$ but is weaker when $n>2r$.