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

From TCS Wiki
Jump to navigation Jump to search
imported>WikiSysop
imported>WikiSysop
Line 1: Line 1:
== Sperner system ==
== Sperner system ==
A set family <math>\mathcal{F}\subseteq 2^X</math> with the relation <math>\subseteq</math> define a poset. Thus, a '''chain''' is a sequence <math>S_1\subseteq S_2\subseteq\cdots\subseteq S_k</math>.
A set family <math>\mathcal{F}\subseteq 2^X</math> is an '''antichain''' (also called a '''Sperner system''') if for all <math>S,T\in\mathcal{F}</math> that <math>S\neq T</math>, we have <math>S\not\subseteq T</math>.
{{Theorem|Theorem (Sperner 1928)|
{{Theorem|Theorem (Sperner 1928)|
:Let <math>\mathcal{F}\subseteq 2^X</math> where <math>|X|=n</math>. If <math>\mathcal{F}</math> is an antichain, then
:Let <math>\mathcal{F}\subseteq 2^X</math> where <math>|X|=n</math>. If <math>\mathcal{F}</math> is an antichain, then

Revision as of 09:12, 30 October 2010

Sperner system

A set family [math]\displaystyle{ \mathcal{F}\subseteq 2^X }[/math] with the relation [math]\displaystyle{ \subseteq }[/math] define a poset. Thus, a chain is a sequence [math]\displaystyle{ S_1\subseteq S_2\subseteq\cdots\subseteq S_k }[/math].

A set family [math]\displaystyle{ \mathcal{F}\subseteq 2^X }[/math] is an antichain (also called a Sperner system) if for all [math]\displaystyle{ S,T\in\mathcal{F} }[/math] that [math]\displaystyle{ S\neq T }[/math], we have [math]\displaystyle{ S\not\subseteq T }[/math].

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

Definition (sunflower)
A set family [math]\displaystyle{ \mathcal{F}\subseteq 2^X }[/math] is a sunflower of size [math]\displaystyle{ r }[/math] with a core [math]\displaystyle{ C\subseteq X }[/math] if
[math]\displaystyle{ \forall S,T\in\mathcal{F} }[/math] that [math]\displaystyle{ S\neq T }[/math], [math]\displaystyle{ S\cap T=C }[/math].

Note that we do not require the core to be nonempty, thus a family of disjoint sets is also a sunflower (with the core [math]\displaystyle{ \emptyset }[/math]).

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].
Proof.

We proceed by induction on [math]\displaystyle{ k }[/math]. For [math]\displaystyle{ k=1 }[/math], [math]\displaystyle{ \mathcal{F}\subseteq{X\choose 1} }[/math], thus all sets in [math]\displaystyle{ \mathcal{F} }[/math] are disjoint. And since [math]\displaystyle{ |\mathcal{F}|\gt r-1 }[/math], we can choose [math]\displaystyle{ r }[/math] of these sets and form a sunflower.

Now let [math]\displaystyle{ k\ge 2 }[/math] and assume the lemma holds for all smaller [math]\displaystyle{ k }[/math]. Take a maximal family [math]\displaystyle{ \mathcal{G}\subseteq \mathcal{F} }[/math] whose members are disjoint, i.e. for any [math]\displaystyle{ S,T\in \mathcal{G} }[/math] that [math]\displaystyle{ S\neq T }[/math], [math]\displaystyle{ S\cap T=\emptyset }[/math].

If [math]\displaystyle{ |\mathcal{G}|\ge r }[/math], then [math]\displaystyle{ \mathcal{G} }[/math] is a sunflower of size at least [math]\displaystyle{ r }[/math] and we are done.

Assume that [math]\displaystyle{ |\mathcal{G}|\le r-1 }[/math], and let [math]\displaystyle{ Y=\bigcup_{S\in\mathcal{G}}S }[/math]. Then [math]\displaystyle{ |Y|=k|\mathcal{G}|\le k(r-1) }[/math] (since all members of [math]\displaystyle{ \mathcal{G} }[/math]) are disjoint). We claim that [math]\displaystyle{ Y }[/math] intersets all members of [math]\displaystyle{ \mathcal{F} }[/math], since if otherwise, there exists an [math]\displaystyle{ S\in\mathcal{F} }[/math] such that [math]\displaystyle{ S\cap Y=\emptyset }[/math], then we can enlarge [math]\displaystyle{ \mathcal{G} }[/math] by adding [math]\displaystyle{ S }[/math] into [math]\displaystyle{ \mathcal{G} }[/math] and still have all members of [math]\displaystyle{ \mathcal{G} }[/math] disjoint, which contradicts the assumption that [math]\displaystyle{ \mathcal{G} }[/math] is the maximum of such families.

By the pigeonhole principle, some elements [math]\displaystyle{ y\in Y }[/math] must contained in at least

[math]\displaystyle{ \frac{|\mathcal{F}|}{|Y|}\gt \frac{k!(r-1)^k}{k(r-1)}=(k-1)!(r-1)^{k-1} }[/math]

members of [math]\displaystyle{ \mathcal{F} }[/math]. We delete this [math]\displaystyle{ y }[/math] from these sets and consider the family

[math]\displaystyle{ \mathcal{H}=\{S\setminus\{y\}\mid S\in\mathcal{F}\wedge y\in S\} }[/math].

We have [math]\displaystyle{ \mathcal{H}\subseteq {X\choose k-1} }[/math] and [math]\displaystyle{ |\mathcal{H}|\gt (k-1)!(r-1)^{k-1} }[/math], thus by the induction hypothesis, [math]\displaystyle{ \mathcal{H} }[/math]contains a sunflower of size [math]\displaystyle{ r }[/math]. Adding [math]\displaystyle{ y }[/math] to the members of this sunflower, we get the desired sunflower in the original family [math]\displaystyle{ \mathcal{F} }[/math].

[math]\displaystyle{ \square }[/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

Definition (shifting)
For [math]\displaystyle{ |X|=n }[/math], [math]\displaystyle{ \mathcal{F}\subseteq 2^X }[/math] and [math]\displaystyle{ 1\le i\lt j\le n }[/math], define the [math]\displaystyle{ (i,j) }[/math]-shift [math]\displaystyle{ S_{ij} }[/math] as an operator on [math]\displaystyle{ \mathcal{F} }[/math] and the sets [math]\displaystyle{ T\in\mathcal{F} }[/math] as follows:
  • for each [math]\displaystyle{ T\in\mathcal{F} }[/math], write [math]\displaystyle{ T_{ij}=(T\setminus\{j\})\cup\{i\} }[/math], and let
[math]\displaystyle{ S_{ij}(T)= \begin{cases} T_{ij} & \mbox{if }j\in T, i\not\in T, \mbox{ and }T_{ij} \not\in\mathcal{F},\\ T & \mbox{otherwise;} \end{cases} }[/math]
  • let [math]\displaystyle{ S_{ij}(\mathcal{F})=\{S_{ij}(T)\mid T\in \mathcal{F}\} }[/math].
Proposition
  1. [math]\displaystyle{ |S_{ij}(T)|=|T| }[/math] and [math]\displaystyle{ |S_{ij}(\mathcal{F})|=\mathcal{F} }[/math];
  2. if [math]\displaystyle{ \mathcal{F} }[/math] is intersecting, then so is [math]\displaystyle{ S_{ij}(\mathcal{F}) }[/math].