Combinatorics (Fall 2010)/Extremal set theory II

Sauer's lemma and VC-dimension

Shattering

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

Down-shifts

Definition (down-shifts)

Assume [math]\displaystyle{ \mathcal{F}\subseteq 2^{[n]} }[/math], and [math]\displaystyle{ i\in[n] }[/math]. Define the down-shift operator [math]\displaystyle{ S_{i} }[/math] as follows: for each [math]\displaystyle{ T\in\mathcal{F} }[/math], let [math]\displaystyle{ 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]\displaystyle{ S_{i}(\mathcal{F})=\{S_{i}(T)\mid T\in \mathcal{F}\} }[/math].

Proposition

[math]\displaystyle{ |S_{i}(\mathcal{F})|=\mathcal{F} }[/math]; [math]\displaystyle{ S_i(\mathcal{F})|_R\subseteq S_i(\mathcal{F}|_R) }[/math], thus [math]\displaystyle{ |S_i(\mathcal{F})|_R|\le |\mathcal{F}|_R| }[/math].

Proof. 1 is immediate. We prove 2, that [math]\displaystyle{ S_i(\mathcal{F})|_R\subseteq S_i(\mathcal{F}|_R) }[/math]. File:Down-shift-property.png [math]\displaystyle{ \square }[/math]

The Vapnik-Chervonenkis dimenison

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

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

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

Proposition

[math]\displaystyle{ \Delta S_{ij}(\mathcal{F})\subseteq S_{ij}(\Delta\mathcal{F}) }[/math].

Proof. We abuse the notation [math]\displaystyle{ \Delta }[/math] and let [math]\displaystyle{ \Delta A=\Delta\{A\} }[/math] if [math]\displaystyle{ A }[/math] is a set instead of a set system. It is sufficient to show that for any [math]\displaystyle{ A\in\mathcal{F} }[/math], [math]\displaystyle{ \Delta S_{ij}(A)\subseteq S_{ij}(\Delta\mathcal{F}) }[/math]. File:Property-shift-shadow.jpg [math]\displaystyle{ \square }[/math]

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

Corollary

[math]\displaystyle{ |\Delta S_{ij}(\mathcal{F})|\le |\Delta\mathcal{F}| }[/math].

Proof. By the above proposition, [math]\displaystyle{ |\Delta S_{ij}(\mathcal{F})|\le|S_{ij}(\Delta\mathcal{F})| }[/math], and we know that [math]\displaystyle{ S_{ij} }[/math] does not change the cardinality of a set family, that is, [math]\displaystyle{ |S_{ij}(\Delta\mathcal{F})|=|\Delta\mathcal{F}| }[/math], therefore [math]\displaystyle{ \Delta S_{ij}(\mathcal{F})|\le|\Delta\mathcal{F}| }[/math]. [math]\displaystyle{ \square }[/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]\displaystyle{ \mathcal{F} }[/math]. We then assume [math]\displaystyle{ \mathcal{F} }[/math] is shifted.

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 regarding the size of the shadow.

Claim 1

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

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

Proof. If [math]\displaystyle{ A\in\Delta\mathcal{F}_0 }[/math] then [math]\displaystyle{ A\cup\{j\}\in\mathcal{F}_0\subseteq\mathcal{F} }[/math] for some [math]\displaystyle{ j\gt 1 }[/math] so that, since [math]\displaystyle{ \mathcal{F} }[/math] is shifted, applying the [math]\displaystyle{ (1,j) }[/math]-shift [math]\displaystyle{ S_{1j} }[/math], [math]\displaystyle{ A\cup\{1\}\in\mathcal{F} }[/math], thus, [math]\displaystyle{ A\in\mathcal{F}_1' }[/math]. [math]\displaystyle{ \square }[/math]

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

Claim 3

If [math]\displaystyle{ \mathcal{F} }[/math] is shifted, then [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].

Proof. 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'|\\ &\gt \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]\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}\gt |\mathcal{F}_1'| }[/math]. On the other hand, by Claim 2, [math]\displaystyle{ |\mathcal{F}_1'|\ge|\Delta\mathcal{F}_0| }[/math]. Thus [math]\displaystyle{ |\mathcal{F}_1'|\ge|\Delta\mathcal{F}_0|\gt |\mathcal{F}_1'| }[/math], a contradiction. [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]

Lovász's simplification

Recall that

[math]\displaystyle{ {x\choose k}=\frac{x(x-1)\cdots(x-k+1)}{k!} }[/math]

can be defined for any real values of [math]\displaystyle{ x }[/math].

Theorem (Lovász)

Let [math]\displaystyle{ \mathcal{F}\subseteq {X\choose k} }[/math] with [math]\displaystyle{ |\mathcal{F}|=m }[/math], and suppose that [math]\displaystyle{ m={x\choose k} }[/math] for some real number [math]\displaystyle{ x\ge k }[/math]. Then [math]\displaystyle{ |\Delta\mathcal{F}|\ge {x\choose k-1} }[/math].

Consequences of Kruskal-Katona

Corollary

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 for all [math]\displaystyle{ r }[/math], [math]\displaystyle{ 1\le r\le k }[/math], [math]\displaystyle{ \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].

The Erdős–Ko–Rado theorem

Erdős–Ko–Rado theorem (proved in 1938, published in 1961)

Let [math]\displaystyle{ \mathcal{F}\subseteq {X\choose k} }[/math] where [math]\displaystyle{ |X|=n }[/math] and [math]\displaystyle{ n\ge 2k }[/math]. If [math]\displaystyle{ \mathcal{F} }[/math] is intersecting, then [math]\displaystyle{ |\mathcal{F}|\le{n-1\choose k-1} }[/math].

Proof of Erdős–Ko–Rado theorem by Kruskal-Katona theorem (Daykin 1974, Clements 1976) [math]\displaystyle{ \square }[/math]

A two-family theorem

Theorem (Kleitman 1986)

Let [math]\displaystyle{ \mathcal{A}\subseteq {X\choose k} }[/math] and [math]\displaystyle{ \mathcal{B}\subseteq {X\choose \ell} }[/math], [math]\displaystyle{ |X|=n }[/math] and [math]\displaystyle{ k+\ell\le n }[/math]. If for any [math]\displaystyle{ A\in\mathcal{A} }[/math] and [math]\displaystyle{ B\in\mathcal{B} }[/math], [math]\displaystyle{ A\cap B\neq\emptyset }[/math], then either [math]\displaystyle{ |\mathcal{A}|\le{n-1\choose k-1} }[/math] or [math]\displaystyle{ |\mathcal{B}|\lt {n-1\choose \ell-1} }[/math].

Proof. (Hilton 1977) [math]\displaystyle{ \square }[/math]