LYM Inequality

A simple proof.

We start with universe $[n]=\{1,\ldots,n\}$, and consider families of sets ${\cal F}\subseteq 2^{[n]}$. Such a family is called an antichain when its sets are not related by $\subset$; that is, $F_1 \not\subset F_2$ for all $F_1,F_2\in{\cal F}$. Sperner's Theorem says that, for any antichain ${\cal F}$, $$|{\cal F}| \le \binom{n}{\lfloor n/2 \rfloor}$$ and it is a consequence of the more general LYM inequality, which also holds for antichains: $$\sum_{F \in {\cal F}} \binom{n}{|F|}^{-1} \le 1$$

It is easy to see that Sperner follows from LYM because $\binom{n}{\lfloor n/2 \rfloor} \ge \binom{n}{k}$ for all $n$ and $k$. It is perhaps not so easy to see why the LYM inequality holds. Here is a proof by induction on $n$. The base case $n=0$ is easy. Otherwise, we can assume the induction hypothesis $$\sum_{\substack{F\\ F\in{\cal F}\\x\not\in F}} \binom{n-1}{|F|}^{-1} \le 1$$ for any $x\in[n]$. Then $$\begin{aligned} 1 \;&\ge\; \frac{1}{n} \sum_{x \in [n]} \sum_{\substack{F\\ F\in{\cal F}\\x\not\in F}} \binom{n-1}{|F|}^{-1} &&\text{average induction hypothesis over all $x\in [n]$} \\\;&=\; \frac{1}{n} \sum_{x \in [n]} \sum_{\substack{F\in{\cal F}}} [x\not\in F] \binom{n-1}{|F|}^{-1} &&\text{use indicator function $[{\cdot}]$} \\\;&=\; \sum_{\substack{F\in{\cal F}}} \frac{1}{n} \binom{n-1}{|F|}^{-1} \sum_{x \in [n]} [x\not\in F] &&\text{swap sums} \\\;&=\; \sum_{\substack{F\in{\cal F}}} \frac{1}{n} \binom{n-1}{|F|}^{-1} (n-|F|) &&\text{compute the inner sum} \\\;&=\; \sum_{\substack{F\in{\cal F}}} \binom{n}{|F|}^{-1} &&\text{property of binomial coefficients} \end{aligned}$$

We just proved the LYM inequality. Or did we? Where did I use that ${\cal F}$ is an antichain? I didn't, so the proof above must be wrong. Can you find the mistake and fix it? (Hint: The mistake is subtle but silly, the fix is simple.)

[toggle answer]

The problem is in the step that introduces the indicator function $[{\cdot}]$. That can be done only if $\binom{n-1}{|F|}\ne 0$. This happens most of the time, except when $|F|=n$. Such a case must be treated separately. If $|F|=n$ then $|{\cal F}|=1$ because ${\cal F}$ is an antichain. (There — we used the antichain property.) Thus, the inequality holds for this case as well.