Sperner's theorem: Difference between revisions
New page: '''Sperner's theorem''': Any line-free subset of <math>[2]^n</math> has cardinality at most <math>\binom{n}{\lfloor n/2\rfloor}</math>. It implies the k=2 version of the [[density Ha... |
No edit summary |
||
| Line 9: | Line 9: | ||
The k=3 generalisation of this inequality is the [[hyper-optimistic conjecture]]. | The k=3 generalisation of this inequality is the [[hyper-optimistic conjecture]]. | ||
The LYM inequality can be proven as follows. Randomly shuffle the n indices and then consider the intersection of A with the strings <math>0^i 1^{n-i}</math> for <math>i=0,\ldots,n</math>. As A is line-free, at most one of these strings lie in A. 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. | ||
* | * [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] | ||
Revision as of 10:41, 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.
