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

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


{{Prooftitle|Proof of Kruskal-Katonal theorem|(due to Frankl, by the shifting technique)
{{Prooftitle|Proof of Kruskal-Katonal theorem|(due to Frankl, by the shifting technique)
Assume <math>\mathcal{F}</math> is shifted.
Assume <math>\mathcal{F}</math> is shifted. We know that shifts never enlarge the shadow, thus it is sufficient to prove the theorem for shifted <math>\mathcal{F}</math>.


Apply induction on <math>m</math> and for given <math>m</math> on <math>k</math>. The theorem holds trivially for the case that <math>k=1</math> and <math>m</math> is arbitrary.
Apply induction on <math>m</math> and for given <math>m</math> on <math>k</math>. The theorem holds trivially for the case that <math>k=1</math> and <math>m</math> is arbitrary.
Line 51: Line 51:
:<math>|\mathcal{F}|=|\mathcal{F}_0|+|\mathcal{F}_1|=|\mathcal{F}_0|+|\mathcal{F}_1'|</math>.
:<math>|\mathcal{F}|=|\mathcal{F}_0|+|\mathcal{F}_1|=|\mathcal{F}_0|+|\mathcal{F}_1'|</math>.


We then make the following claim:
Our induction is based on the following observation of the size of the shadow of <math>\mathcal{F}</math>.
{{Theorem|Claim 1|
<math>|\Delta(\mathcal{F})|\ge|\Delta(\mathcal{F}_1')|+|\mathcal{F}_1'|</math>.
}}
{{Proofbox|
Obviously <math>\mathcal{F}\supseteq\mathcal{F}_1</math> and <math>\Delta(\mathcal{F})\supseteq\Delta(\mathcal{F}_1)</math>.
:<math>\begin{align}
\Delta(\mathcal{F}_1)
&=\left\{A\in{X\choose k-1}\,\,\bigg|\,\, \exists B\in\mathcal{F}_1, A\subset B\right\}\\
&=\left\{A\in{X\choose k-1}\,\,\bigg|\,\, 1\in A, \exists B\in\mathcal{F}_1, A\subset B\right\}\\
&\quad\, \cup \left\{A\in{X\choose k-1}\,\,\bigg|\,\, 1\not\in A, \exists B\in\mathcal{F}_1, A\subset B\right\}\\
&=\{S\cup\{1\}\mid S\in\Delta(\mathcal{F}_1')\}\cup\mathcal{F}_1'.
\end{align}</math>
The union is taken over two disjoint families. Therefore,
:<math>|\Delta(\mathcal{F})|\ge|\Delta(\mathcal{F})_1|=|\Delta(\mathcal{F}_1')|+|\mathcal{F}_1'|</math>.
}}


{{Theorem|Claim 1|
The following property of shifted <math>\mathcal{F}</math> is essential for our proof.
{{Theorem|Claim 2|
For shifted <math>\mathcal{F}</math>, it holds that <math>\Delta(\mathcal{F}_0)\subseteq \mathcal{F}_1'</math>.
For shifted <math>\mathcal{F}</math>, it holds that <math>\Delta(\mathcal{F}_0)\subseteq \mathcal{F}_1'</math>.
}}
}}
Line 60: Line 76:
}}
}}


Our next claim is:
We then bound the size of <math>\mathcal{F}_1'</math> as:


{{Theorem|Claim 2|
{{Theorem|Claim 3|
<math>|\mathcal{F}_1'|\ge{m_k-1\choose k-1}+{m_{k-1}-1\choose k-2}+\cdots+{m_t-1\choose t-1}</math>.
<math>|\mathcal{F}_1'|\ge{m_k-1\choose k-1}+{m_{k-1}-1\choose k-2}+\cdots+{m_t-1\choose t-1}</math>.
}}
}}
Line 78: Line 94:
If <math>m_k>t</math>, then by the induction hypothesis, we have  
If <math>m_k>t</math>, then by the induction hypothesis, we have  
:<math>|\Delta(\mathcal{F}_0)|\ge{m_k-1\choose k-1}+{m_{k-1}-1\choose k-1}+\cdots+{m_t-1\choose t-1}</math>,
:<math>|\Delta(\mathcal{F}_0)|\ge{m_k-1\choose k-1}+{m_{k-1}-1\choose k-1}+\cdots+{m_t-1\choose t-1}</math>,
and due to Claim 1, we have <math>|\mathcal{F}_1'|\ge|\Delta(\mathcal{F}_0)|\ge{m_k-1\choose k-1}+\cdots+{m_t-1\choose t-1}</math>, contradicting.
and due to Claim 2, we have <math>|\mathcal{F}_1'|\ge|\Delta(\mathcal{F}_0)|\ge{m_k-1\choose k-1}+\cdots+{m_t-1\choose t-1}</math>, contradicting.


If <math>m_k=t</math>, then let <math>s</math> be the largest integer so that <math>m_s=s</math> holds, <math>k\ge s\ge t</math>. Then  
If <math>m_k=t</math>, then let <math>s</math> be the largest integer so that <math>m_s=s</math> holds, <math>k\ge s\ge t</math>. Then  
Line 94: Line 110:
&={m_k-1\choose k-1}+{m_{k-1}-1\choose k-1}+\cdots+{m_{t}-1\choose t-1},
&={m_k-1\choose k-1}+{m_{k-1}-1\choose k-1}+\cdots+{m_{t}-1\choose t-1},
\end{align}</math>
\end{align}</math>
again by Claim 1 <math>|\mathcal{F}_1'|\ge|\Delta(\mathcal{F}_0)|</math>, in contradiction to the assumption  
again by Claim 2 <math>|\mathcal{F}_1'|\ge|\Delta(\mathcal{F}_0)|</math>, in contradiction to the assumption  
:<math>|\mathcal{F}_1'|<{m_k-1\choose k-1}+\cdots+{m_t-1\choose t-1}</math>.
:<math>|\mathcal{F}_1'|<{m_k-1\choose k-1}+\cdots+{m_t-1\choose t-1}</math>.
}}
}}


The shadow of <math>\mathcal{F}</math> is lower bounded as follows.
Now we officially apply the induction. By Claim 1,  
 
:<math>|\Delta(\mathcal{F})|\ge|\Delta(\mathcal{F}_1')|+|\mathcal{F}_1'|</math>.
{{Theorem|Claim 3|
Note that <math>\mathcal{F}_1'\subseteq{X\choose k-1}</math>, and due to Claim 3,  
<math>|\Delta(\mathcal{F})|\ge|\Delta(\mathcal{F}_1')|+|\mathcal{F}_1'|</math>.
}}
{{Proofbox|
Obviously <math>\mathcal{F}\supseteq\mathcal{F}_1</math> and <math>\Delta(\mathcal{F})\supseteq\Delta(\mathcal{F}_1)</math>.
:<math>\begin{align}
\Delta(\mathcal{F}_1)
&=\left\{A\in{X\choose k-1}\,\,\bigg|\,\, \exists B\in\mathcal{F}_1, A\subset B\right\}\\
&=\left\{A\in{X\choose k-1}\,\,\bigg|\,\, 1\in A, \exists B\in\mathcal{F}_1, A\subset B\right\}\\
&\quad\, \cup \left\{A\in{X\choose k-1}\,\,\bigg|\,\, 1\not\in A, \exists B\in\mathcal{F}_1, A\subset B\right\}\\
&=\{S\cup\{1\}\mid S\in\Delta(\mathcal{F}_1')\}\cup\mathcal{F}_1'.
\end{align}</math>
The union is taken over two disjoint families. Therefore,
:<math>|\Delta(\mathcal{F})|\ge|\Delta(\mathcal{F})_1|=|\Delta(\mathcal{F}_1')|+|\mathcal{F}_1'|</math>.
}}
Note that <math>\mathcal{F}_1'\subseteq{X\choose k-1}</math>. Due to Claim 2,  
:<math>|\mathcal{F}_1'|\ge{m_k-1\choose k-1}+{m_{k-1}-1\choose k-2}+\cdots+{m_t-1\choose t-1}</math>,  
:<math>|\mathcal{F}_1'|\ge{m_k-1\choose k-1}+{m_{k-1}-1\choose k-2}+\cdots+{m_t-1\choose t-1}</math>,  
thus by the induction hypothesis,  
thus by the induction hypothesis,  

Revision as of 10:01, 6 November 2010

Intersecting Families

Erdős–Ko–Rado theorem

Katona's theorem

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

The Kruskal–Katona Theorem

Theorem (Kruskal 1963, Katona 1966)
Let [math]\displaystyle{ \mathcal{F}\subseteq {X\choose k} }[/math] with [math]\displaystyle{ |\mathcal{F}|=m }[/math], and suppose that
[math]\displaystyle{ m={m_k\choose k}+{m_{k-1}\choose k-1}+\cdots+{m_t\choose t} }[/math]
where [math]\displaystyle{ m_k\gt m_{k-1}\gt \cdots\gt m_t\ge t\ge 1 }[/math]. Then
[math]\displaystyle{ |\Delta\mathcal{F}|\ge {m_k\choose k-1}+{m_{k-1}\choose k-2}+\cdots+{m_t\choose t-1} }[/math].
Proposition
[math]\displaystyle{ \Delta(S_{ij}(\mathcal{F}))\subseteq S_{ij}(\Delta(\mathcal{F})) }[/math].
Proof.
[math]\displaystyle{ \square }[/math]
Corollary
[math]\displaystyle{ |\Delta(S_{ij}(\mathcal{F}))|\le |S_{ij}(\Delta(\mathcal{F}))|=|\Delta(\mathcal{F})| }[/math].
Proof of Kruskal-Katonal theorem
(due to Frankl, by the shifting technique)

Assume [math]\displaystyle{ \mathcal{F} }[/math] is shifted. We know that shifts never enlarge the shadow, thus it is sufficient to prove the theorem for shifted [math]\displaystyle{ \mathcal{F} }[/math].

Apply induction on [math]\displaystyle{ m }[/math] and for given [math]\displaystyle{ m }[/math] on [math]\displaystyle{ k }[/math]. The theorem holds trivially for the case that [math]\displaystyle{ k=1 }[/math] and [math]\displaystyle{ m }[/math] is arbitrary.

Define

[math]\displaystyle{ \mathcal{F}_0=\{A\in\mathcal{F}\mid 1\not\in A\} }[/math],
[math]\displaystyle{ \mathcal{F}_1=\{A\in\mathcal{F}\mid 1\in A\} }[/math].

And let [math]\displaystyle{ \mathcal{F}_1'=\{A\setminus\{1\}\mid A\in\mathcal{F}_1\} }[/math].

Clearly [math]\displaystyle{ \mathcal{F}_0,\mathcal{F}_1\subseteq{X\choose k} }[/math], [math]\displaystyle{ \mathcal{F}_1'\subseteq{X\choose k-1} }[/math], and

[math]\displaystyle{ |\mathcal{F}|=|\mathcal{F}_0|+|\mathcal{F}_1|=|\mathcal{F}_0|+|\mathcal{F}_1'| }[/math].

Our induction is based on the following observation of the size of the shadow of [math]\displaystyle{ \mathcal{F} }[/math].

Claim 1

[math]\displaystyle{ |\Delta(\mathcal{F})|\ge|\Delta(\mathcal{F}_1')|+|\mathcal{F}_1'| }[/math].

Obviously [math]\displaystyle{ \mathcal{F}\supseteq\mathcal{F}_1 }[/math] and [math]\displaystyle{ \Delta(\mathcal{F})\supseteq\Delta(\mathcal{F}_1) }[/math].

[math]\displaystyle{ \begin{align} \Delta(\mathcal{F}_1) &=\left\{A\in{X\choose k-1}\,\,\bigg|\,\, \exists B\in\mathcal{F}_1, A\subset B\right\}\\ &=\left\{A\in{X\choose k-1}\,\,\bigg|\,\, 1\in A, \exists B\in\mathcal{F}_1, A\subset B\right\}\\ &\quad\, \cup \left\{A\in{X\choose k-1}\,\,\bigg|\,\, 1\not\in A, \exists B\in\mathcal{F}_1, A\subset B\right\}\\ &=\{S\cup\{1\}\mid S\in\Delta(\mathcal{F}_1')\}\cup\mathcal{F}_1'. \end{align} }[/math]

The union is taken over two disjoint families. Therefore,

[math]\displaystyle{ |\Delta(\mathcal{F})|\ge|\Delta(\mathcal{F})_1|=|\Delta(\mathcal{F}_1')|+|\mathcal{F}_1'| }[/math].
[math]\displaystyle{ \square }[/math]

The following property of shifted [math]\displaystyle{ \mathcal{F} }[/math] is essential for our proof.

Claim 2

For shifted [math]\displaystyle{ \mathcal{F} }[/math], it holds that [math]\displaystyle{ \Delta(\mathcal{F}_0)\subseteq \mathcal{F}_1' }[/math].

By contradiction, assume that there exists an [math]\displaystyle{ A }[/math] such that [math]\displaystyle{ A\in\Delta(\mathcal{F}_0) }[/math] but [math]\displaystyle{ A\not\in\mathcal{F}_1' }[/math]. Then obviously [math]\displaystyle{ 1\not\in A }[/math]; [math]\displaystyle{ A\in\Delta(\mathcal{F}_0) }[/math] implies that there exists a [math]\displaystyle{ j\neq 1 }[/math], [math]\displaystyle{ j\not\in A }[/math], such that [math]\displaystyle{ A\cup\{j\}\in \mathcal{F}_0 }[/math]; and [math]\displaystyle{ A\not\in\mathcal{F}_1' }[/math] implies that [math]\displaystyle{ A\cup\{1\}\not\in\mathcal{F}_1 }[/math]. Denoting [math]\displaystyle{ B=A\cup\{j\} }[/math] and [math]\displaystyle{ B_{1j}=B\setminus\{j\}\cup\{1\}=A\cup\{1\} }[/math], from the above argument, we have that [math]\displaystyle{ B\in\mathcal{F} }[/math] and [math]\displaystyle{ B_{1j}\not\in\mathcal{F} }[/math], which contradicts that [math]\displaystyle{ \mathcal{F} }[/math] is shifted.

[math]\displaystyle{ \square }[/math]

We then bound the size of [math]\displaystyle{ \mathcal{F}_1' }[/math] as:

Claim 3

[math]\displaystyle{ |\mathcal{F}_1'|\ge{m_k-1\choose k-1}+{m_{k-1}-1\choose k-2}+\cdots+{m_t-1\choose t-1} }[/math].

By contradiction, assume that

[math]\displaystyle{ |\mathcal{F}_1'|\lt {m_k-1\choose k-1}+{m_{k-1}-1\choose k-2}+\cdots+{m_t-1\choose t-1} }[/math].

Then by [math]\displaystyle{ |\mathcal{F}|=|\mathcal{F}_0|+|\mathcal{F}_1'| }[/math], it holds that

[math]\displaystyle{ \begin{align} |\mathcal{F}_0| &=m-|\mathcal{F}_1'|\\ &\ge {m_k\choose k}+{m_{k-1}\choose k-1}+\cdots+{m_t\choose t}\\ &\quad\,- {m_k-1\choose k-1}-{m_{k-1}-1\choose k-2}-\cdots-{m_t-1\choose t-1}+1\\ &={m_k-1\choose k}+{m_{k-1}-1\choose k-1}+\cdots+{m_t-1\choose t}+1. \end{align} }[/math]

If [math]\displaystyle{ m_k\gt t }[/math], then by the induction hypothesis, we have

[math]\displaystyle{ |\Delta(\mathcal{F}_0)|\ge{m_k-1\choose k-1}+{m_{k-1}-1\choose k-1}+\cdots+{m_t-1\choose t-1} }[/math],

and due to Claim 2, we have [math]\displaystyle{ |\mathcal{F}_1'|\ge|\Delta(\mathcal{F}_0)|\ge{m_k-1\choose k-1}+\cdots+{m_t-1\choose t-1} }[/math], contradicting.

If [math]\displaystyle{ m_k=t }[/math], then let [math]\displaystyle{ s }[/math] be the largest integer so that [math]\displaystyle{ m_s=s }[/math] holds, [math]\displaystyle{ k\ge s\ge t }[/math]. Then

[math]\displaystyle{ \begin{align} |\mathcal{F}_0| &\ge{m_k-1\choose k}+{m_{k-1}-1\choose k-1}+\cdots+{m_t-1\choose t}+1\\ &\ge {m_k-1\choose k}+{m_{k-1}-1\choose k-1}+\cdots+{m_{s+1}-1\choose s+1}+{s\choose s}. \end{align} }[/math]

By the induction hypothesis, we have

[math]\displaystyle{ \begin{align} |\Delta(\mathcal{F}_0)| &\ge{m_k-1\choose k-1}+{m_{k-1}-1\choose k-1}+\cdots+{m_{s+1}-1\choose s}+{s\choose s-1}\\ &\ge{m_k-1\choose k-1}+{m_{k-1}-1\choose k-1}+\cdots+{m_{s+1}-1\choose s}+(s-t+1)\\ &={m_k-1\choose k-1}+{m_{k-1}-1\choose k-1}+\cdots+{m_{t}-1\choose t-1}, \end{align} }[/math]

again by Claim 2 [math]\displaystyle{ |\mathcal{F}_1'|\ge|\Delta(\mathcal{F}_0)| }[/math], in contradiction to the assumption

[math]\displaystyle{ |\mathcal{F}_1'|\lt {m_k-1\choose k-1}+\cdots+{m_t-1\choose t-1} }[/math].
[math]\displaystyle{ \square }[/math]

Now we officially apply the induction. By Claim 1,

[math]\displaystyle{ |\Delta(\mathcal{F})|\ge|\Delta(\mathcal{F}_1')|+|\mathcal{F}_1'| }[/math].

Note that [math]\displaystyle{ \mathcal{F}_1'\subseteq{X\choose k-1} }[/math], and due to Claim 3,

[math]\displaystyle{ |\mathcal{F}_1'|\ge{m_k-1\choose k-1}+{m_{k-1}-1\choose k-2}+\cdots+{m_t-1\choose t-1} }[/math],

thus by the induction hypothesis,

[math]\displaystyle{ |\Delta(\mathcal{F}_1')|\ge{m_k-1\choose k-2}+{m_{k-1}-1\choose k-3}+\cdots+{m_t-1\choose t-2} }[/math].

Combining them together, we have

[math]\displaystyle{ \begin{align} |\Delta(\mathcal{F})| &\ge |\Delta(\mathcal{F}_1')|+|\mathcal{F}_1'|\\ &\ge {m_k-1\choose k-2}+\cdots+{m_t-1\choose t-2}+{m_k-1\choose k-1}+\cdots+{m_t-1\choose t-1}\\ &= {m_k\choose k-1}+{m_{k-1}\choose k-2}+\cdots+{m_t\choose t-1}. \end{align} }[/math]
[math]\displaystyle{ \square }[/math]