Past exam of the mathematics course of the University of Cambridge / 2013 / iii / Paper 10 / 1 / Solution

Write $[n{]}^{(r)}$ for the rank-$r$ uniform layer of the Boolean cube. For a uniform set family $\mathcal{F}\subseteq [n{]}^{(r)}$, with $1\le r\le n$, let $\partial \mathcal{F}$ be its lower shadow. The Local LYM inequality isFor its proof, count incidences $(B,A)$ with $A\in \mathcal{F}$, $B\subset A$, and $|B|=r-1$. Each member of $\mathcal{F}$ contributes $r$ incidences, while each member of the lower shadow contributes at most $n-r+1$. Thus $r|\mathcal{F}|\le (n-r+1)|\partial \mathcal{F}|$, which is the displayed bound by the ratio of consecutive binomial coefficients. Complementing every set gives the corresponding upper shadow bound, $|\nabla \mathcal{F}|/\left(\genfrac{}{}{0ex}{}{n}{r+1}\right)\ge |\mathcal{F}|/(\genfrac{}{}{0ex}{}{n}{r})$ for $r<n$.

For an antichain $\mathcal{A}$ in the Boolean lattice, the LYM inequality isHere is the proof using the Local LYM inequality. Denote the rank-$r$ part by ${\mathcal{A}}_r$, and let ${\mathcal{D}}_r$ consist of the $r$-sets containing some member of $\mathcal{A}$ of size at most $r$. These families satisfyThe union is disjoint because a member of the antichain cannot contain a strictly smaller member. Apply the upper shadow form of the Local LYM inequality to ${\mathcal{D}}_{r-1}$:Iterating gives a bound for the entire sum by $|{\mathcal{D}}_n|/(\genfrac{}{}{0ex}{}{n}{n})\le 1$. This also covers the empty antichain and an antichain containing the empty set.

For the second proof, each permutation of $[n]$ specifies a maximal chain in a Boolean lattice by taking its successive prefixes. There are $n!$ such maximal chains in a Boolean lattice, and a fixed $r$-set belongs to $r!(n-r)!$ of them. A maximal chain in a Boolean lattice meets an antichain at most once. Double counting these incidences therefore gives ${\sum }_r|{\mathcal{A}}_r|r!(n-r)!\le n!$, exactly the LYM inequality.

The Sperner theorem says that an antichain in $\mathcal{P}([n])$ has at most $\left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$ members; a full middle rank attains this bound. Indeed, every binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$ is at most the central one, so the LYM inequality givesNow let $\mathcal{F}$ be an intersection-free uniform set family. If it is empty, there is nothing to prove. Fix $X\in \mathcal{F}$ and consider the tracesIf $A,B\ne X$ are distinct and $X\cap A\subseteq X\cap B$, then $X\cap A\subseteq B$. This contradicts the defining restriction on the three distinct members $X,A,B$. The intersection has size less than $r$, so it is a proper subset of $B$ even if the printed subset symbol is interpreted strictly. In particular, equal traces are impossible, and the traces form an antichain. Thus $|\mathcal{T}|=|\mathcal{F}|-1$. Applying the Sperner theorem to the $r$-element ground set $X$ proves the antichain trace bound for intersection-free familiesThe argument also handles $r=0$: a uniform set family then has at most one member.