View source for Combinatorics (Fall 2010)/Extremal set theory II

== Sauer's lemma and VC-dimension ==

=== Shattering ===
{{Theorem|Definition|
:Let <math>\mathcal{F}\subseteq 2^X</math> be set family and let <math>R\subseteq X</math> be a subset. The '''trace''' of <math>\mathcal{F}</math> on <math>R</math>, denoted <math>\mathcal{F}|_R</math> is defined as
::<math>\mathcal{F}|_R=\{S\cap R\mid S\in\mathcal{F}\}</math>.
:We say that <math>\mathcal{F}</math> '''shatters''' <math>R</math> if <math>\mathcal{F}|_R=2^R</math>, i.e. for all <math>T\subseteq R</math>, there exists an <math>S\in\mathcal{F}</math> such that <math>T=S\cap R</math>.
}}

{{Theorem|Sauer's Lemma (Sauer; Shelah-Perles; Vapnik-Chervonenkis)|
:Let <math>\mathcal{F}\subseteq 2^X</math> where <math>|X|=n</math>. If <math>|\mathcal{F}|>\sum_{1\le i<k}{n\choose i}</math>, then there exists an <math>R\in{X\choose k}</math> such that <math>\mathcal{F}</math> shatters <math>R</math>.
}}

=== Down-shifts ===
{{Theorem|Definition (down-shifts)|
: Assume <math>\mathcal{F}\subseteq 2^{[n]}</math>, and <math>i\in[n]</math>. Define the '''down-shift''' operator <math>S_{i}</math> as follows:
:* for each <math>T\in\mathcal{F}</math>, let
::<math>S_{i}(T)=
\begin{cases}
T\setminus\{i\} & \mbox{if }i\in T \mbox{ and }T\setminus\{i\} \not\in\mathcal{F},\\
T & \mbox{otherwise;}
\end{cases}</math>
:* let <math>S_{i}(\mathcal{F})=\{S_{i}(T)\mid T\in \mathcal{F}\}</math>.
}}

{{Theorem|Proposition|
# <math>|S_{i}(\mathcal{F})|=\mathcal{F}</math>;
# <math>S_i(\mathcal{F})|_R\subseteq S_i(\mathcal{F}|_R)</math>, thus <math>|S_i(\mathcal{F})|_R|\le |\mathcal{F}|_R|</math>.
}}
{{Proof|
1 is immediate. We prove 2, that <math>S_i(\mathcal{F})|_R\subseteq S_i(\mathcal{F}|_R)</math>.

[[file:Down-shift-property.png|600px]]
}}

=== The Vapnik-Chervonenkis dimenison ===

{{Theorem|Definition (VC-dimension)|
:The '''Vapnik–Chervonenkis dimension''' ('''VC-dimension''') of a set family <math>\mathcal{F}\subseteq 2^X</math>, denoted <math>\text{VC-dim}(\mathcal{F})</math>, is the size of the largest <math>R\subseteq X</math> shattered by <math>\mathcal{F}</math>.
}}

== The Kruskal–Katona Theorem ==

=== <math>k</math>-cascade representation of a number ===
{{Theorem|Theorem|
:Given positive integers <math>m</math> and <math>k</math>, there exists a unique representation of <math>m</math> in the form
::<math>m={m_k\choose k}+{m_{k-1}\choose k-1}+\cdots+{m_t\choose t}=\sum_{\ell=t}^k{m_\ell\choose \ell}</math>,
:where <math>m_k>m_{k-1}>\cdots>m_t\ge t\ge 1</math>.
:This representation of <math>m</math> is called a '''<math>k</math>-cascade''' (or a '''<math>k</math>-binomial''') representation of <math>m</math>. 
}}
{{Proof|
In fact, the <math>k</math>-cascade representation <math>(m_k,m_{k-1},\ldots,m_t)</math> of an <math>m</math> can be found by the following simple greedy algorithm:
 <math>\ell=k;</math>
 while (<math>m>0</math>) do
     let <math>m_\ell</math> be the largest integer for which <math>{m_\ell\choose \ell}\le m;</math>
     <math>m=m-m_\ell;</math>
     <math>\ell=\ell-1;</math>
 end

We then show that the above algorithm constructs a sequence <math>(m_k,m_{k-1},\ldots,m_t)</math> with <math>m_k>m_{k-1}>\cdots>m_t\ge t\ge 1</math>.

Suppose the current <math>\ell</math> and the current <math>m</math>. To see that <math>m_{\ell-1}< m_\ell</math>, we suppose otherwise <math>m_{\ell-1}\ge m_\ell</math>. Then 
:<math>m\ge {m_\ell\choose \ell}+{m_{\ell-1}\choose \ell-1}\ge{m_\ell\choose \ell}+{m_{\ell}\choose \ell-1}={1+m_{\ell}\choose \ell}</math>
contradicting the maximality of <math>m_\ell</math>. Therefore, <math>m_\ell>m_{\ell-1}</math>.

The algorithm continues reducing <math>m</math> to smaller nonnegative values, and eventually reaches a stage where the choice of <math>m_t</math> for some <math>t\ge 2</math> where <math>{m_t\choose t}</math> equals the current <math>m</math>; or gets right down to choosing <math>m_1</math> as the integer such that <math>m_1={m_1\choose 1}</math> equals the current <math>m</math>.

Therefore,  <math>m={m_k\choose k}+{m_{k-1}\choose k-1}+\cdots+{m_t\choose t}</math> and <math>m_k>m_{k-1}>\cdots>m_t\ge t\ge 1</math>.

The uniqueness of the <math>k</math>-cascade representation follows by the induction on <math>k</math>.

When <math>k=1</math>, <math>m</math> has a unique <math>k</math>-cascade representation <math>m={m\choose 1}</math>.

For general <math>k>1</math>, suppose that every nonnegative integer <math>m</math> has a unique <math>(k-1)</math>-cascade representation.

Suppose then that <math>m</math> has two <math>k</math>-cascade representations:
:<math>m={a_k\choose k}+{a_{k-1}\choose k-1}+\cdots+{a_t\choose t}={b_k\choose k}+{b_{k-1}\choose k-1}+\cdots+{b_r\choose r}</math>.
We then show that it must hold that <math>a_k=b_k</math>.
If <math>a_k\neq b_k</math>, WLOG, suppose that <math>a_k<b_k</math>. We obtain
:<math>
\begin{align}
m&
={a_k\choose k}+{a_{k-1}\choose k-1}+\cdots+{a_t\choose t}\\
&\le {a_k\choose k}+{a_{k}-1\choose k-1}+\cdots+{a_k-(k-t)\choose t}+\cdots+{a_k-k+1\choose 1}\\
&={a_k+1\choose k}-1,
\end{align}</math>
by repeatedly applying the identity
:<math>{n\choose k}+{n\choose k-1}={n+1\choose k}</math>.
We then obtain 
:<math>m<{a_k+1\choose k}\le{b_k\choose k}\le m</math>, 
which is a contradiction. Therefore, <math>a_k=b_k</math>, and by the induction hypothesis, the remaining value <math>m-a_k=m-b_k</math> has a unique <math>(k-1)</math>-cascade representation, so <math>a_i=b_i</math> for all <math>i</math>.
}}

=== Co-lexicographic order of subsets ===
The co-lexicographic order of sets plays a particularly important role in the investigation of the size of the shadow of a system of <math>k</math>-sets.
{{Theorem|Definition|
: The '''co-lexicographic (colex) order''' (also called the '''reverse lexicographic order''') of sets is defined as follows: for any <math>A,B\subseteq [n]</math>, <math>A\neq B</math>,
::<math>A<B</math> if <math>\max A\setminus B < \max B\setminus A</math>.
}}

We can sort sets in colex order by first writing each set as a tuple, whose elements are in decreasing order, and then sorting the tuples in the lexicographic order of tuples.

For example, <math>{[5]\choose 3}</math> in colex order is
 {3,2,1}
 {4,2,1}
 {4,3,1}
 {4,3,2}
 {5,2,1}
 {5,3,1}
 {5,3,2}
 {5,4,1}
 {5,4,2}
 {5,4,3}

We find that the first <math>{n\choose 3}</math> sets in this order for <math>n=3,4,5</math>, form precisely <math>{[n]\choose 3}</math>. And if we write the colex order of <math>{[6]\choose 3}</math>, the above colex order of <math>{[5]\choose 3}</math> appears as a prefix of that order. Elaborating on this, we have:
{{Theorem|Proposition|
:Let <math>\mathcal{R}(m,k)</math> be the first <math>m</math> sets in the colex order of <math>{\mathbb{N}\choose k}</math>. Then 
::<math>\mathcal{R}\left({n\choose k},k\right)={[n]\choose k}</math>,
:that is, the first <math>{n\choose k}</math> sets in the colex order of all <math>k</math>-sets of natural numbers is precisely <math>{[n]\choose k}</math>.
}}

This proposition says that the sets in <math>\mathcal{R}(m,k)</math> is highly overlapped, which suggests that <math>\mathcal{R}(m,k)</math> may have small shadow. The size of the shadow of <math>\mathcal{R}(m,k)</math> is closely related to the <math>k</math>-cascade representation of <math>m</math>.

{{Theorem|Theorem|
:Suppose the <math>k</math>-cascade representation of <math>m</math> is 
::<math>m={m_k\choose k}+{m_{k-1}\choose k-1}+\cdots+{m_t\choose t}</math>.
:Then
::<math>|\Delta\mathcal{R}(m,k)|={m_k\choose k-1}+{m_{k-1}\choose k-2}+\cdots+{m_t\choose t-1}</math>.
}}
{{Proof|
Given <math>m</math> and its <math>k</math>-cascade representation <math>m={m_k\choose k}+{m_{k-1}\choose k-1}+\cdots+{m_t\choose t}</math>, the <math>\mathcal{R}(m,k)</math> is constructed as:
* all sets in <math>{[m_k]\choose k}</math>;
* all sets in <math>{[m_{k-1}]\choose k-1}</math>, unioned with <math>\{1+m_k\}\,</math>;
::<math>\vdots</math>
* all sets in <math>{[m_{t}]\choose t}</math>, unioned with <math>\{1+m_k,1+m_{k-1},\ldots,1+m_{t+1}\}</math>.
The shadow <math>\Delta\mathcal{R}(m,k)</math> is the collection of all <math>(k-1)</math>-sets contained by the above sets, which are
* all sets in <math>{[m_k]\choose k-1}</math>;
* all sets in <math>{[m_{k-1}]\choose k-2}</math>, unioned with <math>\{1+m_k\}\,</math>;
::<math>\vdots</math>
* all sets in <math>{[m_{t}]\choose t-1}</math>, unioned with <math>\{1+m_k,1+m_{k-1},\ldots,1+m_{t+1}\}</math>.
Thus,
:<math>|\Delta\mathcal{R}(m,k)|={m_k\choose k-1}+{m_{k-1}\choose k-2}+\cdots+{m_t\choose t-1}</math>.
}}

=== The Kruskal–Katona theorem ===
{{Theorem|Theorem (Kruskal 1963, Katona 1966)|
:Let <math>\mathcal{F}\subseteq {X\choose k}</math> with <math>|\mathcal{F}|=m</math>, and suppose that
::<math>m={m_k\choose k}+{m_{k-1}\choose k-1}+\cdots+{m_t\choose t}</math>
:where <math>m_k>m_{k-1}>\cdots>m_t\ge t\ge 1</math>. Then
::<math>|\Delta\mathcal{F}|\ge {m_k\choose k-1}+{m_{k-1}\choose k-2}+\cdots+{m_t\choose t-1}</math>.
}}

;Frankl's shifting proof of Kruskal-Katonal theorem (Frankl 1984)

{{Theorem|Proposition|
:<math>\Delta S_{ij}(\mathcal{F})\subseteq S_{ij}(\Delta\mathcal{F})</math>.
}}
{{Proof|
We abuse the notation <math>\Delta</math> and let <math>\Delta A=\Delta\{A\}</math> if <math>A</math> is a set instead of a set system.

It is sufficient to show that for any <math>A\in\mathcal{F}</math>, <math>\Delta S_{ij}(A)\subseteq S_{ij}(\Delta\mathcal{F})</math>.

[[file:Property-shift-shadow.png|600px]]
}}

An immediate corollary of the above proposition is that the <math>(i,j)</math>-shifts <math>S_{ij}</math> for any <math>1\le i<j\le n</math> do not increase the size of the shadow.

{{Theorem|Corollary|
:<math>|\Delta S_{ij}(\mathcal{F})|\le |\Delta\mathcal{F}|</math>.
}}
{{Proof|
By the above proposition, <math>|\Delta S_{ij}(\mathcal{F})|\le|S_{ij}(\Delta\mathcal{F})|</math>, and we know that <math>S_{ij}</math> does not change the cardinality of a set family, that is, <math>|S_{ij}(\Delta\mathcal{F})|=|\Delta\mathcal{F}|</math>, therefore <math>\Delta S_{ij}(\mathcal{F})|\le|\Delta\mathcal{F}|</math>.
}}

;Proof of Kruskal-Katona theorem
We know that shifts never enlarge the shadow, thus it is sufficient to prove the theorem for shifted <math>\mathcal{F}</math>. We then assume <math>\mathcal{F}</math> is shifted.

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.

Define 
:<math>\mathcal{F}_0=\{A\in\mathcal{F}\mid 1\not\in A\}</math>, 
:<math>\mathcal{F}_1=\{A\in\mathcal{F}\mid 1\in A\}</math>.
And let <math>\mathcal{F}_1'=\{A\setminus\{1\}\mid A\in\mathcal{F}_1\}</math>.

Clearly <math>\mathcal{F}_0,\mathcal{F}_1\subseteq{X\choose k}</math>, <math>\mathcal{F}_1'\subseteq{X\choose k-1}</math>, and
:<math>|\mathcal{F}|=|\mathcal{F}_0|+|\mathcal{F}_1|=|\mathcal{F}_0|+|\mathcal{F}_1'|</math>.

Our induction is based on the following observation regarding the size of the shadow.
{{Theorem|Lemma 1|
:<math>|\Delta\mathcal{F}|\ge|\Delta\mathcal{F}_1'|+|\mathcal{F}_1'|</math>.
}}
{{Proof|
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>.
}}

The following property of shifted <math>\mathcal{F}</math> is essential for our proof.
{{Theorem|Lemma 2|
:For shifted <math>\mathcal{F}</math>, it holds that <math>\Delta\mathcal{F}_0\subseteq \mathcal{F}_1'</math>.
}}
{{Proof|
If <math>A\in\Delta\mathcal{F}_0</math> then <math>A\cup\{j\}\in\mathcal{F}_0\subseteq\mathcal{F}</math> for some <math>j>1</math> so that, since <math>\mathcal{F}</math> is shifted, applying the <math>(1,j)</math>-shift <math>S_{1j}</math>, <math>A\cup\{1\}\in\mathcal{F}</math>, thus, <math>A\in\mathcal{F}_1'</math>.
}}

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

{{Theorem|Lemma 3|
:If <math>\mathcal{F}</math> is shifted, then
::<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>.
}}
{{Proof|
By contradiction, assume that
:<math>|\mathcal{F}_1'|<{m_k-1\choose k-1}+{m_{k-1}-1\choose k-2}+\cdots+{m_t-1\choose t-1}</math>.
Then by <math>|\mathcal{F}|=|\mathcal{F}_0|+|\mathcal{F}_1'|</math>, it holds that
:<math>
\begin{align}
|\mathcal{F}_0| &=m-|\mathcal{F}_1'|\\
&>\left\{{m_k\choose k}- {m_k-1\choose k-1}\right\}+\cdots+\left\{{m_t\choose t}- {m_t-1\choose t-1}\right\}\\
&={m_k-1\choose k}+\cdots+{m_t-1\choose t},
\end{align}</math>
so that, by the induction hypothesis, 
:<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}>|\mathcal{F}_1'|</math>.
On the other hand, by Lemma 2, <math>|\mathcal{F}_1'|\ge|\Delta\mathcal{F}_0|</math>. Thus <math>|\mathcal{F}_1'|\ge|\Delta\mathcal{F}_0|>|\mathcal{F}_1'|</math>, a contradiction.
}}

Now we officially apply the induction. By Lemma 1, 
:<math>|\Delta\mathcal{F}|\ge|\Delta\mathcal{F}_1'|+|\mathcal{F}_1'|</math>.
Note that <math>\mathcal{F}_1'\subseteq{X\choose k-1}</math>, and due to Lemma 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>, 
thus by the induction hypothesis, 
:<math>|\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>
\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>\square</math>

=== Shadows of specific sizes ===

{{Theorem|Kruskal-Katona Theorem (general version)|
:Let <math>\mathcal{F}\subseteq {X\choose k}</math> with <math>|\mathcal{F}|=m</math>, and suppose that
::<math>m={m_k\choose k}+{m_{k-1}\choose k-1}+\cdots+{m_t\choose t}</math>
:where <math>m_k>m_{k-1}>\cdots>m_t\ge t\ge 1</math>. Then for all <math>r</math>, <math>1\le r\le k</math>,
::<math>\left|\Delta_r\mathcal{F}\right|\ge {m_k\choose r}+{m_{k-1}\choose r-1}+\cdots+{m_t\choose t-k+r}</math>.
}}

=== Erdős–Ko–Rado theorem ===

{{Theorem|Erdős–Ko–Rado theorem (proved in 1938, published in 1961)|
:Let <math>\mathcal{F}\subseteq {X\choose k}</math> where <math>|X|=n</math> and <math>n\ge 2k</math>. If <math>\mathcal{F}</math> is intersecting, then
::<math>|\mathcal{F}|\le{n-1\choose k-1}</math>.
}}

{{Prooftitle|Proof of Erdős–Ko–Rado theorem by Kruskal-Katona theorem|(Daykin 1974, Clements 1976)
}}