20 April 2018

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.


Dominic Orchard said...
This comment has been removed by the author.
Dominic Orchard said...

(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

Radu Grigore said...

Hi Dominic! It's induction on the size of the universe.
Sorry for nerd-snipping you.

Lance Fortnow said...

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}.

Radu Grigore said...

@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.