LYM inequality

cosmos 29th October 2017 at 11:35pm
Antichain Extremal combinatorics Power set

named after Lubell, Yamamoto and Meshalkin, who all gave independent proofs of the result

Let FP(n)F \subseteq P(n) be an Antichain. Then

i=0nF[n](i)(ni)1\sum\limits_{i=0}^n \frac{|F \cap [n]^{(i)}|}{\binom{n}{i}} \leq 1

where [n](i) [n]^{(i)} is the ith layer of the Power set P(n)P(n). Furthermore, we have equality if and only if F=[n](i)F = [n]^{(i)} for some ii.

Sperner's lemma can be easily deduced from LYM inequality. It shows that there is only equality in Sperner's lemma when the antichain is [n](n/2)[n]^{(\lfloor n/2\rfloor)}.

Consequences: For instance, if we take 100% of the subsets at one layer, than that summand is 1, and so we can't take any at any other layer (which makes sense, as then it would be comparable to some element, and it wouldn't be an antichain).

If we take 90% at some layer, we can't take more than 10% at another layer, etc.

See full proofs here (second proof is quite slick)

Local LYM inequality

Let A[n](r)A \subseteq [n]^{(r)}. Then

A(nr1)A(nr)\frac{|\partial A|}{\binom{n}{r-1}} \geq \frac{|A|}{\binom{n}{r}}

We have equality if and only if A=A= \emptyset or A=[n](r)A = [n]^{(r)}, where A\partial A is the lower shadow of AA.

That is the fraction of sets in the shadow of a collection (relative to all sets in its layer of power set) is greater than or equal to the fraction of sets in the collection.


This somehow has a similar feeling to Kraft inequality