Combinatorics (Fall 2010)/Extremal set theory

From TCS Wiki
Revision as of 10:52, 27 October 2010 by imported>WikiSysop (→‎Erdős–Ko–Rado theorem)
Jump to navigation Jump to search

Sperner system

Theorem (Sperner 1928)
Let [math]\displaystyle{ \mathcal{F}\subseteq 2^X }[/math] where [math]\displaystyle{ |X|=n }[/math]. If [math]\displaystyle{ \mathcal{F} }[/math] is an antichain, then
[math]\displaystyle{ |\mathcal{F}|\le{n\choose \lfloor n/2\rfloor} }[/math].

First proof (shadows)

Definition
Let [math]\displaystyle{ |X|=n\, }[/math] and [math]\displaystyle{ \mathcal{F}\subseteq {X\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\{T\in {X\choose k+1}\,\,\bigg|\,\, \exists S\in\mathcal{F}\mbox{ such that } S\subset T\right\} }[/math].
Thus the shade [math]\displaystyle{ \nabla\mathcal{F} }[/math] of [math]\displaystyle{ \mathcal{F} }[/math] consists of all subsets of [math]\displaystyle{ X }[/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\{T\in {X\choose k-1}\,\,\bigg|\,\, \exists S\in\mathcal{F}\mbox{ such that } T\subset S\right\} }[/math].
Thus the shadow [math]\displaystyle{ \Delta\mathcal{F} }[/math] of [math]\displaystyle{ \mathcal{F} }[/math] consists of all subsets of [math]\displaystyle{ X }[/math] which can be obtained by removing an element from a set in [math]\displaystyle{ \mathcal{F} }[/math].
Lemma (Sperner)
Let [math]\displaystyle{ |X|=n\, }[/math] and [math]\displaystyle{ \mathcal{F}\subseteq {X\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{ \mathcal{F}\subseteq 2^X }[/math] where [math]\displaystyle{ |X|=n }[/math], and let [math]\displaystyle{ f_k=|\{S\in\mathcal{F}\mid |S|=k\}| }[/math], for [math]\displaystyle{ k=0,1,\ldots,n }[/math].
If [math]\displaystyle{ \mathcal{F} }[/math] is an antichain, then
[math]\displaystyle{ \sum_{S\in\mathcal{F}}\frac{1}{{n\choose |S|}}=\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_{S\in\mathcal{F}}\frac{1}{{n\choose |S|}}\le 1 }[/math] implies that [math]\displaystyle{ |\mathcal{F}|\le{n\choose \lfloor n/2\rfloor} }[/math].

Intersecting Families

Sunflowers

Sunflower Lemma
Let [math]\displaystyle{ \mathcal{F}\subseteq {X\choose k} }[/math]. If [math]\displaystyle{ |\mathcal{F}|\gt k!(r-1)^k }[/math], then [math]\displaystyle{ \mathcal{F} }[/math] contains a sunflower of size [math]\displaystyle{ r }[/math].

Erdős–Ko–Rado theorem

Erdős–Ko–Rado theorem
Let [math]\displaystyle{ \mathcal{F}\subseteq {X\choose k} }[/math] where [math]\displaystyle{ |X|=n }[/math]. If for any [math]\displaystyle{ S,T\in\mathcal{F} }[/math], [math]\displaystyle{ S\cap T\neq\emptyset }[/math], then
[math]\displaystyle{ |\mathcal{F}|\le{n-1\choose k-1} }[/math].

Katona's proof

Erdős' shifting technique

Sauer's lemma and VC-dimension

Definition
Let [math]\displaystyle{ \mathcal{F}\subseteq 2^X }[/math] be set family and let [math]\displaystyle{ R\subseteq X }[/math] be a subset. The restriction of [math]\displaystyle{ \mathcal{F} }[/math] on [math]\displaystyle{ R }[/math], denoted [math]\displaystyle{ \mathcal{F}|_R }[/math] is defined as
[math]\displaystyle{ \mathcal{F}|_R=\{S\cap R\mid S\in\mathcal{F}\} }[/math].
We say that [math]\displaystyle{ \mathcal{F} }[/math] shatters [math]\displaystyle{ R }[/math] if [math]\displaystyle{ \mathcal{F}|_R=2^R }[/math], i.e. for all [math]\displaystyle{ T\subseteq R }[/math], there exists an [math]\displaystyle{ S\in\mathcal{F} }[/math] such that [math]\displaystyle{ T=S\cap R }[/math].
Sauer's Lemma (Sauer; Shelah-Perles; Vapnik-Chervonenkis)
Let [math]\displaystyle{ \mathcal{F}\subseteq 2^X }[/math] where [math]\displaystyle{ |X|=n }[/math]. If [math]\displaystyle{ |\mathcal{F}|\gt \sum_{1\le i\lt k}{n\choose i} }[/math], then there exists an [math]\displaystyle{ R\in{X\choose k} }[/math] such that [math]\displaystyle{ \mathcal{F} }[/math] shatters [math]\displaystyle{ R }[/math].
Definition (VC-dimension)
The Vapnik–Chervonenkis dimension (VC-dimension) of a set family [math]\displaystyle{ \mathcal{F}\subseteq 2^X }[/math], denoted [math]\displaystyle{ \text{VC-dim}(\mathcal{F}) }[/math], is the size of the largest [math]\displaystyle{ R\subseteq X }[/math] shattered by [math]\displaystyle{ \mathcal{F} }[/math].