Combinatorics (Fall 2010)/Extremal set theory: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>WikiSysop
imported>WikiSysop
Line 40: Line 40:
}}
}}


{{Prooftitle|Third proof (the probabilistic method)|
{{Prooftitle|Third proof (the probabilistic method)| (Due to Alon.)
}}
}}



Revision as of 04:40, 26 October 2010

Sperner system

Theorem (Sperner 1928)
Let [math]\displaystyle{ |S|=n }[/math] and [math]\displaystyle{ \mathcal{F}\subseteq 2^S }[/math] be an antichain. Then
[math]\displaystyle{ |\mathcal{F}|\le{n\choose \lfloor n/2\rfloor} }[/math].

First proof (shadowing)

Definition
Let [math]\displaystyle{ |S|=n\, }[/math] and [math]\displaystyle{ \mathcal{F}\subseteq {S\choose k} }[/math], [math]\displaystyle{ k\lt n\, }[/math].
The shade of [math]\displaystyle{ \mathcal{F} }[/math] is defined to be
[math]\displaystyle{ \nabla\mathcal{F}=\left\{A\in {S\choose k+1}\,\,\bigg|\,\, \exists B\in\mathcal{F}\mbox{ such that } B\subset A\right\} }[/math].
Thus the shade [math]\displaystyle{ \nabla\mathcal{F} }[/math] of [math]\displaystyle{ \mathcal{F} }[/math] consists of all subsets of [math]\displaystyle{ S }[/math] which can be obtained by adding an element to a set in [math]\displaystyle{ \mathcal{F} }[/math].
Similarly, the shadow of [math]\displaystyle{ \mathcal{F} }[/math] is defined to be
[math]\displaystyle{ \Delta\mathcal{F}=\left\{A\in {S\choose k-1}\,\,\bigg|\,\, \exists B\in\mathcal{F}\mbox{ such that } A\subset B\right\} }[/math].
Thus the shadow [math]\displaystyle{ \Delta\mathcal{F} }[/math] of [math]\displaystyle{ \mathcal{F} }[/math] consists of all subsets of [math]\displaystyle{ S }[/math] which can be obtained by removing an element from a set in [math]\displaystyle{ \mathcal{F} }[/math].
Lemma (Sperner)
Let [math]\displaystyle{ |S|=n\, }[/math] and [math]\displaystyle{ \mathcal{F}\subseteq {S\choose k} }[/math]. Then
[math]\displaystyle{ \begin{align} &|\nabla\mathcal{F}|\ge\frac{n-k}{k+1}|\mathcal{F}| &\text{ if } k\lt n\\ &|\Delta\mathcal{F}|\ge\frac{k}{n-k+1}|\mathcal{F}| &\text{ if } k\gt 0. \end{align} }[/math]
Proof of Sperner's theorem
(original proof of Sperner)
[math]\displaystyle{ \square }[/math]

Second proof (double counting)

Proof of Sperner's theorem
(Lubell 1966)
[math]\displaystyle{ \square }[/math]

The LYM inequality

Theorem (Lubell, Yamamoto 1954; Meschalkin 1963)
Let [math]\displaystyle{ |S|=n }[/math] and [math]\displaystyle{ \mathcal{F}\subseteq 2^S }[/math] be an antichain. For [math]\displaystyle{ k=0,1,\ldots,n }[/math], let [math]\displaystyle{ f_k=|\{A\in\mathcal{F}\mid |A|=k\}| }[/math]. Then
[math]\displaystyle{ \sum_{A\in\mathcal{F}}\frac{1}{{n\choose |A|}}=\sum_{k=0}^n\frac{f_k}{{n\choose k}}\le 1 }[/math].
Third proof (the probabilistic method)
(Due to Alon.)
[math]\displaystyle{ \square }[/math]
Proposition
[math]\displaystyle{ \sum_{A\in\mathcal{F}}\frac{1}{{n\choose |A|}}\le 1 }[/math] implies that [math]\displaystyle{ |\mathcal{F}|\le{n\choose \lfloor n/2\rfloor} }[/math].

Sunflowers

Erdős–Ko–Rado theorem

Kruskal–Katona theorem