Combinatorics (Fall 2010)/Extremal set theory II

Sauer's lemma and VC-dimension

Shattering and the VC-dimension

Definition (shatter)

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

The VC dimension is defined by the power of a family to shatter a set.

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

It is a core concept in computational learning theory.

Each subset [math]\displaystyle{ S\subseteq X }[/math] can be equivalently represented by its characteristic function [math]\displaystyle{ f_S:X\rightarrow\{0,1\} }[/math], such that for each [math]\displaystyle{ x\in X }[/math],

[math]\displaystyle{ f_S(x)=\begin{cases} 1 & x\in S\\ 0 & x\not\in S. \end{cases} }[/math]

Then a set family [math]\displaystyle{ \mathcal{F}\subseteq2^X }[/math] corresponds to a collection of boolean functions [math]\displaystyle{ \{f_S\mid S\in\mathcal{F}\} }[/math], which is a subset of all Boolean functions in the form [math]\displaystyle{ f:X\rightarrow\{0,1\} }[/math]. We wonder on how large a subdomain [math]\displaystyle{ Y\subseteq X }[/math], [math]\displaystyle{ \mathcal{F} }[/math] includes all the [math]\displaystyle{ 2^{|Y|} }[/math] mappings [math]\displaystyle{ Y\rightarrow\{0,1\} }[/math]. The largest size of such subdomain is the VC-dimension. It measures how complicated a collection of boolean functions (or equivalently a set family) is.

Sauer's Lemma

The definition of the VC-dimension involves enumerating all subsets, thus is difficult to analyze in general. The following famous result state a very simple sufficient condition to lower bound the VC-dimension, regarding only the size of the family. The lemma is due to Sauer, and independently due to Shelah and Perles. A slightly weaker version is found by Vapnik and Chervonenkis, who use the framework to develop a theory of classifications.

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

In other words, for any set family [math]\displaystyle{ \mathcal{F} }[/math] with [math]\displaystyle{ |\mathcal{F}|\gt \sum_{1\le i\lt k}{n\choose i} }[/math], its VC-dimension [math]\displaystyle{ \text{VC-dim}(\mathcal{F})\ge k }[/math].

Hereditary family

We note the Sauer's lemma is especially easy to prove for a special type of set families, called the hereditary families.

Definition (hereditary family)

A set system [math]\displaystyle{ \mathcal{F}\subseteq 2^X }[/math] is said to be hereditary (also called an ideal or an abstract simplicial complex), if [math]\displaystyle{ S\subseteq T\in\mathcal{F} }[/math] implies [math]\displaystyle{ S\in\mathcal{F} }[/math].

In other words, for a hereditary family [math]\displaystyle{ \mathcal{F} }[/math], if [math]\displaystyle{ R\in\mathcal{F} }[/math], then all subsets of [math]\displaystyle{ R }[/math] are also in [math]\displaystyle{ \mathcal{F} }[/math]. An immediate consequence is the following proposition.

Proposition

Let [math]\displaystyle{ \mathcal{F} }[/math] be a hereditary family. If [math]\displaystyle{ R\in\mathcal{F} }[/math] then [math]\displaystyle{ \mathcal{F} }[/math] shatters [math]\displaystyle{ R }[/math].

Therefore, it is very easy to prove the Sauer's lemma for hereditary families:

Lemma

For [math]\displaystyle{ \mathcal{F}\subseteq 2^X }[/math], [math]\displaystyle{ |X|=n }[/math], if [math]\displaystyle{ \mathcal{F} }[/math] is hereditary and [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].

Proof. Since [math]\displaystyle{ \mathcal{F} }[/math] is hereditary, we only need to show that there exists an [math]\displaystyle{ R\in\mathcal{F} }[/math] of size [math]\displaystyle{ |R|\ge k }[/math], which must be true, because if all members of [math]\displaystyle{ \mathcal{F} }[/math] are of sizes [math]\displaystyle{ \lt k }[/math], then [math]\displaystyle{ |\mathcal{F}|\le\left|\bigcup_{1\le i\lt k}{X\choose k}\right|=\sum_{1\le i\lt k}{n\choose i} }[/math], a contradiction. [math]\displaystyle{ \square }[/math]

To prove the Sauer's lemma for general non-hereditary families, we can use some way to reduce arbitrary families to hereditary families. Here we apply the shifting technique to achieve this.

Down-shifts

Note that we work on [math]\displaystyle{ \mathcal{F}\subseteq2^X }[/math], instead of [math]\displaystyle{ \mathcal{F}\subseteq{X\choose k} }[/math] like in the Erdős–Ko–Rado theorem, so we do not need to preserve the size of member sets. Instead, we need to reduce an arbitrary family to a hereditary one, thus we use a shift operator which replaces a member set by a subset of it.

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

Repeatedly applying [math]\displaystyle{ S_i }[/math] to [math]\displaystyle{ \mathcal{F} }[/math] for all [math]\displaystyle{ i\in[n] }[/math], due to the finiteness, eventually [math]\displaystyle{ \mathcal{F} }[/math] is not changed by any [math]\displaystyle{ S_i }[/math]. We call such a family down-shifted. A family [math]\displaystyle{ \mathcal{F} }[/math] is down-shifted if and only if [math]\displaystyle{ S_i(\mathcal{F})=\mathcal{F} }[/math] for all [math]\displaystyle{ i\in[n] }[/math]. It is then easy to see that a down-shifted [math]\displaystyle{ \mathcal{F} }[/math] must be hereditary.

Theorem

If [math]\displaystyle{ \mathcal{F}\subseteq2^X }[/math] is down-shifted, then [math]\displaystyle{ \mathcal{F} }[/math] is hereditary.

In order to use down-shift to prove the Sauer's lemma, we need to make sure that down-shift does not decrease [math]\displaystyle{ |\mathcal{F}| }[/math] and does not increase the VC-dimension [math]\displaystyle{ \text{VC-dim}(\mathcal{F}) }[/math].

Proposition

[math]\displaystyle{ |S_{i}(\mathcal{F})|=\mathcal{F} }[/math]; [math]\displaystyle{ |S_i(\mathcal{F})|_R|\le |\mathcal{F}|_R| }[/math], thus if [math]\displaystyle{ S_{i}(\mathcal{F}) }[/math] shatters an [math]\displaystyle{ R }[/math], so does [math]\displaystyle{ \mathcal{F} }[/math].

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

Proof of Sauer's lemma

Now we can prove the Sauer's lemma for arbitrary [math]\displaystyle{ \mathcal{F}\subseteq 2^{[n]} }[/math].

For any [math]\displaystyle{ \mathcal{F}\subseteq 2^{[n]} }[/math], repeatedly apply [math]\displaystyle{ S_i }[/math] for all [math]\displaystyle{ i\in }[/math] till the family is down-shifted, which is denoted by [math]\displaystyle{ \mathcal{F}' }[/math]. We have proved that [math]\displaystyle{ |\mathcal{F}'|=|\mathcal{F}|\gt \sum_{1\le i\lt k}{n\choose i} }[/math] and [math]\displaystyle{ \mathcal{F}' }[/math] is hereditary, thus as argued before, here exists an [math]\displaystyle{ R }[/math] of size [math]\displaystyle{ k }[/math] shattered by [math]\displaystyle{ \mathcal{F}' }[/math]. By the above proposition, [math]\displaystyle{ |\mathcal{F}'|_R|\le |\mathcal{F}|_R| }[/math], thus [math]\displaystyle{ \mathcal{F} }[/math] also shatters [math]\displaystyle{ R }[/math]. The lemma is proved.

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

The Kruskal–Katona Theorem

The shadow of a set system [math]\displaystyle{ \mathcal{F} }[/math], denoted [math]\displaystyle{ \Delta\mathcal{F} }[/math], consists of all sets which can be obtained by removing an element from a set in [math]\displaystyle{ \mathcal{F} }[/math].

Definition

Let [math]\displaystyle{ \mathcal{F}\subseteq {X\choose k} }[/math]. 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].

The shadow contains rich information about the set system. An extremal question is: for a system of fixed number of [math]\displaystyle{ k }[/math]-sets, how small can its shadow be? The Kruskal–Katona theorem gives an answer to this question.

To state the result of the Kruskal–Katona theorem, we need to introduce the concepts of the [math]\displaystyle{ k }[/math]-cascade representation of numbers and the colex order of sets.

[math]\displaystyle{ k }[/math]-cascade representation of a number

Theorem

Given positive integers [math]\displaystyle{ m }[/math] and [math]\displaystyle{ k }[/math], there exists a unique representation of [math]\displaystyle{ m }[/math] in the form [math]\displaystyle{ 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]\displaystyle{ m_k\gt m_{k-1}\gt \cdots\gt m_t\ge t\ge 1 }[/math]. This representation of [math]\displaystyle{ m }[/math] is called a [math]\displaystyle{ k }[/math]-cascade (or a [math]\displaystyle{ k }[/math]-binomial) representation of [math]\displaystyle{ m }[/math].

Proof. In fact, the [math]\displaystyle{ k }[/math]-cascade representation [math]\displaystyle{ (m_k,m_{k-1},\ldots,m_t) }[/math] of an [math]\displaystyle{ m }[/math] can be found by the following simple greedy algorithm: [math]\displaystyle{ \ell=k; }[/math] while ([math]\displaystyle{ m\gt 0 }[/math]) do let [math]\displaystyle{ m_\ell }[/math] be the largest integer for which [math]\displaystyle{ {m_\ell\choose \ell}\le m; }[/math] [math]\displaystyle{ m=m-m_\ell; }[/math] [math]\displaystyle{ \ell=\ell-1; }[/math] end We then show that the above algorithm constructs a sequence [math]\displaystyle{ (m_k,m_{k-1},\ldots,m_t) }[/math] with [math]\displaystyle{ m_k\gt m_{k-1}\gt \cdots\gt m_t\ge t\ge 1 }[/math]. Suppose the current [math]\displaystyle{ \ell }[/math] and the current [math]\displaystyle{ m }[/math]. To see that [math]\displaystyle{ m_{\ell-1}\lt m_\ell }[/math], we suppose otherwise [math]\displaystyle{ m_{\ell-1}\ge m_\ell }[/math]. Then [math]\displaystyle{ 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]\displaystyle{ m_\ell }[/math]. Therefore, [math]\displaystyle{ m_\ell\gt m_{\ell-1} }[/math]. The algorithm continues reducing [math]\displaystyle{ m }[/math] to smaller nonnegative values, and eventually reaches a stage where the choice of [math]\displaystyle{ m_t }[/math] for some [math]\displaystyle{ t\ge 2 }[/math] where [math]\displaystyle{ {m_t\choose t} }[/math] equals the current [math]\displaystyle{ m }[/math]; or gets right down to choosing [math]\displaystyle{ m_1 }[/math] as the integer such that [math]\displaystyle{ m_1={m_1\choose 1} }[/math] equals the current [math]\displaystyle{ m }[/math]. Therefore, [math]\displaystyle{ m={m_k\choose k}+{m_{k-1}\choose k-1}+\cdots+{m_t\choose t} }[/math] and [math]\displaystyle{ m_k\gt m_{k-1}\gt \cdots\gt m_t\ge t\ge 1 }[/math]. The uniqueness of the [math]\displaystyle{ k }[/math]-cascade representation follows by the induction on [math]\displaystyle{ k }[/math]. When [math]\displaystyle{ k=1 }[/math], [math]\displaystyle{ m }[/math] has a unique [math]\displaystyle{ k }[/math]-cascade representation [math]\displaystyle{ m={m\choose 1} }[/math]. For general [math]\displaystyle{ k\gt 1 }[/math], suppose that every nonnegative integer [math]\displaystyle{ m }[/math] has a unique [math]\displaystyle{ (k-1) }[/math]-cascade representation. Suppose then that [math]\displaystyle{ m }[/math] has two [math]\displaystyle{ k }[/math]-cascade representations: [math]\displaystyle{ 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]\displaystyle{ a_k=b_k }[/math]. If [math]\displaystyle{ a_k\neq b_k }[/math], WLOG, suppose that [math]\displaystyle{ a_k\lt b_k }[/math]. We obtain [math]\displaystyle{ \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] where the last equation is got by repeatedly applying the identity [math]\displaystyle{ {n\choose k}+{n\choose k-1}={n+1\choose k} }[/math]. We then obtain [math]\displaystyle{ m\lt {a_k+1\choose k}\le{b_k\choose k}\le m }[/math], which is a contradiction. Therefore, [math]\displaystyle{ a_k=b_k }[/math], and by the induction hypothesis, the remaining value [math]\displaystyle{ m-a_k=m-b_k }[/math] has a unique [math]\displaystyle{ (k-1) }[/math]-cascade representation, so [math]\displaystyle{ a_i=b_i }[/math] for all [math]\displaystyle{ i }[/math]. [math]\displaystyle{ \square }[/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]\displaystyle{ k }[/math]-sets.

Definition

The co-lexicographic (colex) order (also called the reverse lexicographic order) of sets is defined as follows: for any [math]\displaystyle{ A,B\subseteq [n] }[/math], [math]\displaystyle{ A\neq B }[/math], [math]\displaystyle{ A\lt B }[/math] if [math]\displaystyle{ \max A\setminus B \lt \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]\displaystyle{ {[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]\displaystyle{ {n\choose 3} }[/math] sets in this order for [math]\displaystyle{ n=3,4,5 }[/math], form precisely [math]\displaystyle{ {[n]\choose 3} }[/math]. And if we write the colex order of [math]\displaystyle{ {[6]\choose 3} }[/math], the above colex order of [math]\displaystyle{ {[5]\choose 3} }[/math] appears as a prefix of that order. Elaborating on this, we have:

Proposition

Let [math]\displaystyle{ \mathcal{R}(m,k) }[/math] be the first [math]\displaystyle{ m }[/math] sets in the colex order of [math]\displaystyle{ {\mathbb{N}\choose k} }[/math]. Then [math]\displaystyle{ \mathcal{R}\left({n\choose k},k\right)={[n]\choose k} }[/math], that is, the first [math]\displaystyle{ {n\choose k} }[/math] sets in the colex order of all [math]\displaystyle{ k }[/math]-sets of natural numbers is precisely [math]\displaystyle{ {[n]\choose k} }[/math].

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

Theorem

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

The Kruskal–Katona theorem

The Kruskal–Katona theorem states that among all systems of [math]\displaystyle{ m }[/math] [math]\displaystyle{ k }[/math]-sets, [math]\displaystyle{ \mathcal{R}(m,k) }[/math], i.e., the first [math]\displaystyle{ m }[/math] [math]\displaystyle{ k }[/math]-sets in the colex order, has the smallest shadow.

The theorem is proved independently by Joseph Kruskal in 1963 and G.O.H. Katona in 1966, and is a fundamental result in finite set theory and combinatorial topology.

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

The [math]\displaystyle{ f }[/math]-vector of a set system [math]\displaystyle{ \mathcal{F}\subseteq 2^X }[/math] is a vector [math]\displaystyle{ (|\mathcal{F}_0|,|\mathcal{F}_1|,\ldots,|\mathcal{F}_n|) }[/math] where

[math]\displaystyle{ \mathcal{F}_k=\{S\mid S\in\mathcal{F}, |S|=k\} }[/math],

i.e., the [math]\displaystyle{ f }[/math]-vector gives the number of member sets of each size.

In a hereditary family (also called an abstract simplicial complex), [math]\displaystyle{ \mathcal{F}_k }[/math] is formed by the shadow of [math]\displaystyle{ \mathcal{F}_{k+1} }[/math] as well as some additional [math]\displaystyle{ k }[/math]-sets introduced in this level. The Kruskal-Katona theorem gives a lower bound on [math]\displaystyle{ |\mathcal{F}_i| }[/math], given the [math]\displaystyle{ |\mathcal{F}_{i-1}| }[/math].

The original proof of the theorem is rather complicated. In the following years, several different proofs were discovered. Here we present a proof dueto Frankl by the shifting technique.

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

We take the classic [math]\displaystyle{ (i,j) }[/math]-shift operator [math]\displaystyle{ S_{ij} }[/math] defined in the original proof of the Erdős-Ko-Rado theorem.

Definition ([math]\displaystyle{ (i,j) }[/math]-shift)

Assume [math]\displaystyle{ \mathcal{F}\subseteq 2^{[n]} }[/math], and [math]\displaystyle{ 0\le i\lt j\le n-1 }[/math]. Define the [math]\displaystyle{ (i,j) }[/math]-shift [math]\displaystyle{ S_{ij} }[/math] as an operator on [math]\displaystyle{ \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].

It is immediate that shifting does not change the size of the set or the size of the system, i.e., [math]\displaystyle{ |S_{ij}(T)|=|T|\, }[/math] and [math]\displaystyle{ |S_{ij}(\mathcal{F})|=\mathcal{F} }[/math]. And due to the finiteness, repeatedly applying [math]\displaystyle{ (i,j) }[/math]-shifts for any [math]\displaystyle{ 1\le i\lt j\le n }[/math], eventually [math]\displaystyle{ \mathcal{F} }[/math] does not changing any more. We called such an [math]\displaystyle{ \mathcal{F} }[/math] with [math]\displaystyle{ \mathcal{F}=S_{ij}(\mathcal{F}) }[/math] for any [math]\displaystyle{ 1\le i\lt j\le n }[/math] shifted.

In order to make the shifting technique work for shadows, we have to prove that shifting does not increase the size of the shadow.

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

An immediate corollary of the above proposition 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.

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

Lemma 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:

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

Shadows of specific sizes

The definition of shadow can be generalized to the subsets of any size.

Definition

The [math]\displaystyle{ r }[/math]-shadow of [math]\displaystyle{ \mathcal{F} }[/math] is defined as [math]\displaystyle{ \Delta_r\mathcal{F}=\left\{S\mid |S|=r\text{ and }\exists T\in\mathcal{F}, S\subseteq T\right\} }[/math].

And the general version of the Kruskal-Katona theorem can be deduced.

Kruskal-Katona Theorem (general version)

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

Proof. Note that for [math]\displaystyle{ \mathcal{F}\subseteq {X\choose k} }[/math], [math]\displaystyle{ \Delta_r\mathcal{F}=\underbrace{\Delta\cdots\Delta}_{k-r}\mathcal{F} }[/math]. The theorem follows by repeatedly applying the Kruskal-Katona theorem for [math]\displaystyle{ \Delta\mathcal{F} }[/math]. [math]\displaystyle{ \square }[/math]

The Erdős–Ko–Rado theorem, revisited

To demonstrate the power of the Krulskal-Katona theorem, we show that it actually includes the Erdős–Ko–Rado theorem as a special case. The following elegant proof of the Erdős–Ko–Rado theorem is due to Daykin and Clements independently.

Erdős–Ko–Rado Theorem

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{ S\cap T\neq\emptyset }[/math] for any [math]\displaystyle{ S,T\in\mathcal{F} }[/math], then [math]\displaystyle{ |\mathcal{F}|\le{n-1\choose k-1} }[/math].

Proof by the Kruskal-Katona theorem (Daykin 1974, Clements 1976) By contradiction, suppose that [math]\displaystyle{ |\mathcal{F}|\gt {n-1\choose k-1} }[/math]. We define the dual system [math]\displaystyle{ \mathcal{G}=\{\bar{S}\mid S\in\mathcal{F}\} }[/math], where [math]\displaystyle{ \bar{S}=X\setminus S }[/math]. For any [math]\displaystyle{ S,T\in\mathcal{F} }[/math], the condition [math]\displaystyle{ S\cap T\neq \emptyset }[/math] is equivalent to [math]\displaystyle{ S\not\subseteq \bar{T} }[/math], so [math]\displaystyle{ \mathcal{F} }[/math] and [math]\displaystyle{ \Delta_k\mathcal{G} }[/math] are disjoint, thus [math]\displaystyle{ |\mathcal{F}|+|\Delta_k\mathcal{G}|\le{n\choose k} }[/math]. Clearly, [math]\displaystyle{ \mathcal{G}\subseteq {X\choose n-k} }[/math] and [math]\displaystyle{ |\mathcal{G}|=|\mathcal{F}|\gt {n-1\choose k-1}={n-1\choose n-k} }[/math]. By the Kruskal-Katona theorem, [math]\displaystyle{ |\Delta_k\mathcal{G}|\ge{n-1\choose k} }[/math]. [math]\displaystyle{ |\mathcal{F}|+|\Delta_k\mathcal{G}|\gt {n-1\choose k-1}+{n-1\choose k}={n\choose k} }[/math], a contradiction. [math]\displaystyle{ \square }[/math]