Sperner's theorem: Difference between revisions
No edit summary |
No edit summary |
||
| Line 10: | Line 10: | ||
The LYM inequality can be proven as follows. Randomly shuffle the <math>n</math> indices and then consider the intersection of <math>A</math> with the strings <math>0^i 1^{n-i}</math> for <math>i=0,\ldots,n</math>. As <math>A</math> is line-free, at most one of these strings lie in <math>A</math>. Averaging over all choice of shuffles we obtain the claim. | The LYM inequality can be proven as follows. Randomly shuffle the <math>n</math> indices and then consider the intersection of <math>A</math> with the strings <math>0^i 1^{n-i}</math> for <math>i=0,\ldots,n</math>. As <math>A</math> is line-free, at most one of these strings lie in <math>A</math>. Averaging over all choice of shuffles we obtain the claim. | ||
Sperner's theorem is also related to the [[Kruskal-Katona theorem]]. | |||
* [http://en.wikipedia.org/wiki/Sperner%27s_theorem The Wikipedia entry for Sperner's theorem] | * [http://en.wikipedia.org/wiki/Sperner%27s_theorem The Wikipedia entry for Sperner's theorem] | ||
* [http://en.wikipedia.org/wiki/Lubell-Yamamoto-Meshalkin_inequality The Wikipedia entry for the LYM inequality] | * [http://en.wikipedia.org/wiki/Lubell-Yamamoto-Meshalkin_inequality The Wikipedia entry for the LYM inequality] | ||
Revision as of 16:12, 15 February 2009
Sperner's theorem: Any line-free subset of [math]\displaystyle{ [2]^n }[/math] has cardinality at most [math]\displaystyle{ \binom{n}{\lfloor n/2\rfloor} }[/math].
It implies the k=2 version of the density Hales-Jewett theorem.
A stronger version of Sperner's theorem is
LYM inequality: Any line-free subset of [math]\displaystyle{ [2]^n }[/math] has equal-slices measure at most 1.
The k=3 generalisation of this inequality is the hyper-optimistic conjecture.
The LYM inequality can be proven as follows. Randomly shuffle the [math]\displaystyle{ n }[/math] indices and then consider the intersection of [math]\displaystyle{ A }[/math] with the strings [math]\displaystyle{ 0^i 1^{n-i} }[/math] for [math]\displaystyle{ i=0,\ldots,n }[/math]. As [math]\displaystyle{ A }[/math] is line-free, at most one of these strings lie in [math]\displaystyle{ A }[/math]. Averaging over all choice of shuffles we obtain the claim.
Sperner's theorem is also related to the Kruskal-Katona theorem.
