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.)
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.
5 comments:
(recommend to try to get math to typeset right)
Haven't had a chance to think it through fully, but my immediate reaction was that the inductive hypothesis is wrong. If you are doing induction on `n` then surely you want to say `n ∉ F` rather than `x ∉ F`? I have too much work to be nerd sniped right now though :p
Hi Dominic! It's induction on the size of the universe.
Sorry for nerd-snipping you.
Here's an alternate proof I came up with, though I'm guessing it's already know. Pick a random permutation sigma of {1,...,n}. Let A_F be the event that F = {sigma(1),...,sigma(|F|)}. Probability of A_F is 1/(n choose |F|) and A_F and A_G can't both be true for different F and G in {\cal F}.
@Lance: Nice!
Post a Comment
Note: (1) You need to have third-party cookies enabled in order to comment on Blogger. (2) Better to copy your comment before hitting publish/preview. Blogger sometimes eats comments on the first try, but the second works. Crazy Blogger.