Combinatorics (Fall 2010)/Extremal set theory: Difference between revisions
Jump to navigation
Jump to search
imported>WikiSysop |
imported>WikiSysop No edit summary |
||
Line 1: | Line 1: | ||
== Sperner system == | |||
{{Theorem|Theorem (Sperner 1928)| | |||
:Let <math>|S|=n</math> and <math>\mathcal{F}\subseteq 2^S</math> be an antichain. Then | |||
::<math>|\mathcal{F}|\le{n\choose \lfloor n/2\rfloor}</math>. | |||
}} | |||
=== First proof (symmetric chain decomposition) === | |||
{{Prooftitle|Proof of Sperner's theorem | | |||
}} | |||
=== Second proof (shadowing)=== | |||
{{Theorem|Definition| | |||
:Let <math>|S|=n\,</math> and <math>\mathcal{F}\subseteq {S\choose k}</math>, <math>k<n\,</math>. | |||
:The '''shade''' of <math>\mathcal{F}</math> is defined to be | |||
::<math>\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>\nabla\mathcal{F}</math> of <math>\mathcal{F}</math> consists of all subsets of <math>S</math> which can be obtained by adding an element to a set in <math>\mathcal{F}</math>. | |||
:Similarly, the '''shadow''' of <math>\mathcal{F}</math> is defined to be | |||
::<math>\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>\Delta\mathcal{F}</math> of <math>\mathcal{F}</math> consists of all subsets of <math>S</math> which can be obtained by removing an element from a set in <math>\mathcal{F}</math>. | |||
}} | |||
{{Theorem|Lemma (Sperner)| | |||
:Let <math>|S|=n\,</math> and <math>\mathcal{F}\subseteq {S\choose k}</math>. Then | |||
::<math> | |||
\begin{align} | |||
&|\nabla\mathcal{F}|\ge\frac{n-k}{k+1}|\mathcal{F}| &\text{ if } k<n\\ | |||
&|\Delta\mathcal{F}|\ge\frac{k}{n-k+1}|\mathcal{F}| &\text{ if } k>0. | |||
\end{align} | |||
</math> | |||
}} | |||
{{Prooftitle|Proof of Sperner's theorem | (original proof of Sperner) | |||
}} | |||
=== Third proof (double counting)=== | |||
{{Prooftitle|Proof of Sperner's theorem | (Lubell 1966) | |||
}} | |||
== Sunflowers == | == Sunflowers == | ||
Revision as of 05:16, 22 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].
- Let [math]\displaystyle{ |S|=n }[/math] and [math]\displaystyle{ \mathcal{F}\subseteq 2^S }[/math] be an antichain. Then
First proof (symmetric chain decomposition)
Proof of Sperner's theorem - [math]\displaystyle{ \square }[/math]
Second 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]
- Let [math]\displaystyle{ |S|=n\, }[/math] and [math]\displaystyle{ \mathcal{F}\subseteq {S\choose k} }[/math]. Then
Proof of Sperner's theorem (original proof of Sperner)
- [math]\displaystyle{ \square }[/math]
Third proof (double counting)
Proof of Sperner's theorem (Lubell 1966)
- [math]\displaystyle{ \square }[/math]