# Combinatorics (Fall 2010)/Extremal set theory II

## Sauer's lemma and VC-dimension

### Shattering and the VC-dimension

 Definition (shatter) Let ${\displaystyle {\mathcal {F}}\subseteq 2^{X}}$ be set family and let ${\displaystyle R\subseteq X}$ be a subset. The trace of ${\displaystyle {\mathcal {F}}}$ on ${\displaystyle R}$, denoted ${\displaystyle {\mathcal {F}}|_{R}}$ is defined as ${\displaystyle {\mathcal {F}}|_{R}=\{S\cap R\mid S\in {\mathcal {F}}\}}$. We say that ${\displaystyle {\mathcal {F}}}$ shatters ${\displaystyle R}$ if ${\displaystyle {\mathcal {F}}|_{R}=2^{R}}$, i.e. for all ${\displaystyle T\subseteq R}$, there exists an ${\displaystyle S\in {\mathcal {F}}}$ such that ${\displaystyle T=S\cap R}$.

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 ${\displaystyle {\mathcal {F}}\subseteq 2^{X}}$, denoted ${\displaystyle {\text{VC-dim}}({\mathcal {F}})}$, is the size of the largest ${\displaystyle R\subseteq X}$ shattered by ${\displaystyle {\mathcal {F}}}$.

It is a core concept in computational learning theory.

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

${\displaystyle f_{S}(x)={\begin{cases}1&x\in S\\0&x\not \in S.\end{cases}}}$

Then a set family ${\displaystyle {\mathcal {F}}\subseteq 2^{X}}$ corresponds to a collection of boolean functions ${\displaystyle \{f_{S}\mid S\in {\mathcal {F}}\}}$, which is a subset of all Boolean functions in the form ${\displaystyle f:X\rightarrow \{0,1\}}$. We wonder on how large a subdomain ${\displaystyle Y\subseteq X}$, ${\displaystyle {\mathcal {F}}}$ includes all the ${\displaystyle 2^{|Y|}}$ mappings ${\displaystyle Y\rightarrow \{0,1\}}$. 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 ${\displaystyle {\mathcal {F}}\subseteq 2^{X}}$ where ${\displaystyle |X|=n}$. If ${\displaystyle |{\mathcal {F}}|>\sum _{1\leq i, then there exists an ${\displaystyle R\in {X \choose k}}$ such that ${\displaystyle {\mathcal {F}}}$ shatters ${\displaystyle R}$.

In other words, for any set family ${\displaystyle {\mathcal {F}}}$ with ${\displaystyle |{\mathcal {F}}|>\sum _{1\leq i, its VC-dimension ${\displaystyle {\text{VC-dim}}({\mathcal {F}})\geq k}$.

### 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 ${\displaystyle {\mathcal {F}}\subseteq 2^{X}}$ is said to be hereditary (also called an ideal or an abstract simplicial complex), if ${\displaystyle S\subseteq T\in {\mathcal {F}}}$ implies ${\displaystyle S\in {\mathcal {F}}}$.

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

 Proposition Let ${\displaystyle {\mathcal {F}}}$ be a hereditary family. If ${\displaystyle R\in {\mathcal {F}}}$ then ${\displaystyle {\mathcal {F}}}$ shatters ${\displaystyle R}$.

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

 Lemma For ${\displaystyle {\mathcal {F}}\subseteq 2^{X}}$, ${\displaystyle |X|=n}$, if ${\displaystyle {\mathcal {F}}}$ is hereditary and ${\displaystyle |{\mathcal {F}}|>\sum _{1\leq i then there exists an ${\displaystyle R\in {X \choose k}}$ such that ${\displaystyle {\mathcal {F}}}$ shatters ${\displaystyle R}$.
Proof.
 Since ${\displaystyle {\mathcal {F}}}$ is hereditary, we only need to show that there exists an ${\displaystyle R\in {\mathcal {F}}}$ of size ${\displaystyle |R|\geq k}$, which must be true, because if all members of ${\displaystyle {\mathcal {F}}}$ are of sizes ${\displaystyle , then ${\displaystyle |{\mathcal {F}}|\leq \left|\bigcup _{1\leq i, a contradiction.
${\displaystyle \square }$

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

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

 Theorem If ${\displaystyle {\mathcal {F}}\subseteq 2^{X}}$ is down-shifted, then ${\displaystyle {\mathcal {F}}}$ 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 ${\displaystyle |{\mathcal {F}}|}$ and does not increase the VC-dimension ${\displaystyle {\text{VC-dim}}({\mathcal {F}})}$.

 Proposition ${\displaystyle |S_{i}({\mathcal {F}})|={\mathcal {F}}}$; ${\displaystyle |S_{i}({\mathcal {F}})|_{R}|\leq |{\mathcal {F}}|_{R}|}$, thus if ${\displaystyle S_{i}({\mathcal {F}})}$ shatters an ${\displaystyle R}$, so does ${\displaystyle {\mathcal {F}}}$.
Proof.
 (1) is immediate. To prove (2), it is sufficient to prove that ${\displaystyle S_{i}({\mathcal {F}})|_{R}\subseteq S_{i}({\mathcal {F}}|_{R})}$ and then apply (1).
${\displaystyle \square }$
Proof of Sauer's lemma

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

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

${\displaystyle \square }$

## The Kruskal–Katona Theorem

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

 Definition Let ${\displaystyle {\mathcal {F}}\subseteq {X \choose k}}$. The shadow of ${\displaystyle {\mathcal {F}}}$ is defined to be ${\displaystyle \Delta {\mathcal {F}}=\left\{T\in {X \choose k-1}\,\,{\bigg |}\,\,\exists S\in {\mathcal {F}}{\mbox{ such that }}T\subset S\right\}}$.

The shadow contains rich information about the set system. An extremal question is: for a system of fixed number of ${\displaystyle k}$-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 ${\displaystyle k}$-cascade representation of numbers and the colex order of sets.

### ${\displaystyle k}$-cascade representation of a number

 Theorem Given positive integers ${\displaystyle m}$ and ${\displaystyle k}$, there exists a unique representation of ${\displaystyle m}$ in the form ${\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 }}$, where ${\displaystyle m_{k}>m_{k-1}>\cdots >m_{t}\geq t\geq 1}$. This representation of ${\displaystyle m}$ is called a ${\displaystyle k}$-cascade (or a ${\displaystyle k}$-binomial) representation of ${\displaystyle m}$.
Proof.
 In fact, the ${\displaystyle k}$-cascade representation ${\displaystyle (m_{k},m_{k-1},\ldots ,m_{t})}$ of an ${\displaystyle m}$ can be found by the following simple greedy algorithm: ${\displaystyle \ell =k;}$ while (${\displaystyle m>0}$) do let ${\displaystyle m_{\ell }}$ be the largest integer for which ${\displaystyle {m_{\ell } \choose \ell }\leq m;}$ ${\displaystyle m=m-m_{\ell };}$ ${\displaystyle \ell =\ell -1;}$ end  We then show that the above algorithm constructs a sequence ${\displaystyle (m_{k},m_{k-1},\ldots ,m_{t})}$ with ${\displaystyle m_{k}>m_{k-1}>\cdots >m_{t}\geq t\geq 1}$. Suppose the current ${\displaystyle \ell }$ and the current ${\displaystyle m}$. To see that ${\displaystyle m_{\ell -1}, we suppose otherwise ${\displaystyle m_{\ell -1}\geq m_{\ell }}$. Then ${\displaystyle m\geq {m_{\ell } \choose \ell }+{m_{\ell -1} \choose \ell -1}\geq {m_{\ell } \choose \ell }+{m_{\ell } \choose \ell -1}={1+m_{\ell } \choose \ell }}$ contradicting the maximality of ${\displaystyle m_{\ell }}$. Therefore, ${\displaystyle m_{\ell }>m_{\ell -1}}$. The algorithm continues reducing ${\displaystyle m}$ to smaller nonnegative values, and eventually reaches a stage where the choice of ${\displaystyle m_{t}}$ for some ${\displaystyle t\geq 2}$ where ${\displaystyle {m_{t} \choose t}}$ equals the current ${\displaystyle m}$; or gets right down to choosing ${\displaystyle m_{1}}$ as the integer such that ${\displaystyle m_{1}={m_{1} \choose 1}}$ equals the current ${\displaystyle m}$. Therefore, ${\displaystyle m={m_{k} \choose k}+{m_{k-1} \choose k-1}+\cdots +{m_{t} \choose t}}$ and ${\displaystyle m_{k}>m_{k-1}>\cdots >m_{t}\geq t\geq 1}$. The uniqueness of the ${\displaystyle k}$-cascade representation follows by the induction on ${\displaystyle k}$. When ${\displaystyle k=1}$, ${\displaystyle m}$ has a unique ${\displaystyle k}$-cascade representation ${\displaystyle m={m \choose 1}}$. For general ${\displaystyle k>1}$, suppose that every nonnegative integer ${\displaystyle m}$ has a unique ${\displaystyle (k-1)}$-cascade representation. Suppose then that ${\displaystyle m}$ has two ${\displaystyle k}$-cascade representations: ${\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}}$. We then show that it must hold that ${\displaystyle a_{k}=b_{k}}$. If ${\displaystyle a_{k}\neq b_{k}}$, WLOG, suppose that ${\displaystyle a_{k}. We obtain {\displaystyle {\begin{aligned}m&={a_{k} \choose k}+{a_{k-1} \choose k-1}+\cdots +{a_{t} \choose t}\\&\leq {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{aligned}}} where the last equation is got by repeatedly applying the identity ${\displaystyle {n \choose k}+{n \choose k-1}={n+1 \choose k}}$. We then obtain ${\displaystyle m<{a_{k}+1 \choose k}\leq {b_{k} \choose k}\leq m}$, which is a contradiction. Therefore, ${\displaystyle a_{k}=b_{k}}$, and by the induction hypothesis, the remaining value ${\displaystyle m-a_{k}=m-b_{k}}$ has a unique ${\displaystyle (k-1)}$-cascade representation, so ${\displaystyle a_{i}=b_{i}}$ for all ${\displaystyle i}$.
${\displaystyle \square }$

### 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 ${\displaystyle k}$-sets.

 Definition The co-lexicographic (colex) order (also called the reverse lexicographic order) of sets is defined as follows: for any ${\displaystyle A,B\subseteq [n]}$, ${\displaystyle A\neq B}$, ${\displaystyle A if ${\displaystyle \max A\setminus B<\max B\setminus A}$.

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, ${\displaystyle {[5] \choose 3}}$ 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 ${\displaystyle {n \choose 3}}$ sets in this order for ${\displaystyle n=3,4,5}$, form precisely ${\displaystyle {[n] \choose 3}}$. And if we write the colex order of ${\displaystyle {[6] \choose 3}}$, the above colex order of ${\displaystyle {[5] \choose 3}}$ appears as a prefix of that order. Elaborating on this, we have:

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

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

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

### The Kruskal–Katona theorem

The Kruskal–Katona theorem states that among all systems of ${\displaystyle m}$ ${\displaystyle k}$-sets, ${\displaystyle {\mathcal {R}}(m,k)}$, i.e., the first ${\displaystyle m}$ ${\displaystyle k}$-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 ${\displaystyle {\mathcal {F}}\subseteq {X \choose k}}$ with ${\displaystyle |{\mathcal {F}}|=m}$, and suppose that ${\displaystyle m={m_{k} \choose k}+{m_{k-1} \choose k-1}+\cdots +{m_{t} \choose t}}$ where ${\displaystyle m_{k}>m_{k-1}>\cdots >m_{t}\geq t\geq 1}$. Then ${\displaystyle |\Delta {\mathcal {F}}|\geq {m_{k} \choose k-1}+{m_{k-1} \choose k-2}+\cdots +{m_{t} \choose t-1}}$.

The ${\displaystyle f}$-vector of a set system ${\displaystyle {\mathcal {F}}\subseteq 2^{X}}$ is a vector ${\displaystyle (|{\mathcal {F}}_{0}|,|{\mathcal {F}}_{1}|,\ldots ,|{\mathcal {F}}_{n}|)}$ where

${\displaystyle {\mathcal {F}}_{k}=\{S\mid S\in {\mathcal {F}},|S|=k\}}$,

i.e., the ${\displaystyle f}$-vector gives the number of member sets of each size.

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

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 ${\displaystyle (i,j)}$-shift operator ${\displaystyle S_{ij}}$ defined in the original proof of the Erdős-Ko-Rado theorem.

 Definition (${\displaystyle (i,j)}$-shift) Assume ${\displaystyle {\mathcal {F}}\subseteq 2^{[n]}}$, and ${\displaystyle 0\leq i. Define the ${\displaystyle (i,j)}$-shift ${\displaystyle S_{ij}}$ as an operator on ${\displaystyle {\mathcal {F}}}$ as follows: for each ${\displaystyle T\in {\mathcal {F}}}$, write ${\displaystyle T_{ij}=(T\setminus \{j\})\cup \{i\}}$, and let ${\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}}}$ let ${\displaystyle S_{ij}({\mathcal {F}})=\{S_{ij}(T)\mid T\in {\mathcal {F}}\}}$.

It is immediate that shifting does not change the size of the set or the size of the system, i.e., ${\displaystyle |S_{ij}(T)|=|T|\,}$ and ${\displaystyle |S_{ij}({\mathcal {F}})|={\mathcal {F}}}$. And due to the finiteness, repeatedly applying ${\displaystyle (i,j)}$-shifts for any ${\displaystyle 1\leq i, eventually ${\displaystyle {\mathcal {F}}}$ does not changing any more. We called such an ${\displaystyle {\mathcal {F}}}$ with ${\displaystyle {\mathcal {F}}=S_{ij}({\mathcal {F}})}$ for any ${\displaystyle 1\leq i 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 ${\displaystyle \Delta S_{ij}({\mathcal {F}})\subseteq S_{ij}(\Delta {\mathcal {F}})}$.
Proof.
 We abuse the notation ${\displaystyle \Delta }$ and let ${\displaystyle \Delta A=\Delta \{A\}}$ if ${\displaystyle A}$ is a set instead of a set system. It is sufficient to show that for any ${\displaystyle A\in {\mathcal {F}}}$, ${\displaystyle \Delta S_{ij}(A)\subseteq S_{ij}(\Delta {\mathcal {F}})}$.
${\displaystyle \square }$

An immediate corollary of the above proposition is that the ${\displaystyle (i,j)}$-shifts ${\displaystyle S_{ij}}$ for any ${\displaystyle 1\leq i do not increase the size of the shadow.

 Corollary ${\displaystyle |\Delta S_{ij}({\mathcal {F}})|\leq |\Delta {\mathcal {F}}|}$.
Proof.
 By the above proposition, ${\displaystyle |\Delta S_{ij}({\mathcal {F}})|\leq |S_{ij}(\Delta {\mathcal {F}})|}$, and we know that ${\displaystyle S_{ij}}$ does not change the cardinality of a set family, that is, ${\displaystyle |S_{ij}(\Delta {\mathcal {F}})|=|\Delta {\mathcal {F}}|}$, therefore ${\displaystyle \Delta S_{ij}({\mathcal {F}})|\leq |\Delta {\mathcal {F}}|}$.
${\displaystyle \square }$
Proof of Kruskal-Katona theorem

We know that shifts never enlarge the shadow, thus it is sufficient to prove the theorem for shifted ${\displaystyle {\mathcal {F}}}$. We then assume ${\displaystyle {\mathcal {F}}}$ is shifted.

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

Define

${\displaystyle {\mathcal {F}}_{0}=\{A\in {\mathcal {F}}\mid 1\not \in A\}}$,
${\displaystyle {\mathcal {F}}_{1}=\{A\in {\mathcal {F}}\mid 1\in A\}}$.

And let ${\displaystyle {\mathcal {F}}_{1}'=\{A\setminus \{1\}\mid A\in {\mathcal {F}}_{1}\}}$.

Clearly ${\displaystyle {\mathcal {F}}_{0},{\mathcal {F}}_{1}\subseteq {X \choose k}}$, ${\displaystyle {\mathcal {F}}_{1}'\subseteq {X \choose k-1}}$, and

${\displaystyle |{\mathcal {F}}|=|{\mathcal {F}}_{0}|+|{\mathcal {F}}_{1}|=|{\mathcal {F}}_{0}|+|{\mathcal {F}}_{1}'|}$.

Our induction is based on the following observation regarding the size of the shadow.

 Lemma 1 ${\displaystyle |\Delta {\mathcal {F}}|\geq |\Delta {\mathcal {F}}_{1}'|+|{\mathcal {F}}_{1}'|}$.
Proof.
 Obviously ${\displaystyle {\mathcal {F}}\supseteq {\mathcal {F}}_{1}}$ and ${\displaystyle \Delta {\mathcal {F}}\supseteq \Delta {\mathcal {F}}_{1}}$. {\displaystyle {\begin{aligned}\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{aligned}}} The union is taken over two disjoint families. Therefore, ${\displaystyle |\Delta {\mathcal {F}}|\geq |\Delta {\mathcal {F}}_{1}|=|\Delta {\mathcal {F}}_{1}'|+|{\mathcal {F}}_{1}'|}$.
${\displaystyle \square }$

The following property of shifted ${\displaystyle {\mathcal {F}}}$ is essential for our proof.

 Lemma 2 For shifted ${\displaystyle {\mathcal {F}}}$, it holds that ${\displaystyle \Delta {\mathcal {F}}_{0}\subseteq {\mathcal {F}}_{1}'}$.
Proof.
 If ${\displaystyle A\in \Delta {\mathcal {F}}_{0}}$ then ${\displaystyle A\cup \{j\}\in {\mathcal {F}}_{0}\subseteq {\mathcal {F}}}$ for some ${\displaystyle j>1}$ so that, since ${\displaystyle {\mathcal {F}}}$ is shifted, applying the ${\displaystyle (1,j)}$-shift ${\displaystyle S_{1j}}$, ${\displaystyle A\cup \{1\}\in {\mathcal {F}}}$, thus, ${\displaystyle A\in {\mathcal {F}}_{1}'}$.
${\displaystyle \square }$

We then bound the size of ${\displaystyle {\mathcal {F}}_{1}'}$ as:

 Lemma 3 If ${\displaystyle {\mathcal {F}}}$ is shifted, then ${\displaystyle |{\mathcal {F}}_{1}'|\geq {m_{k}-1 \choose k-1}+{m_{k-1}-1 \choose k-2}+\cdots +{m_{t}-1 \choose t-1}}$.
Proof.
 By contradiction, assume that ${\displaystyle |{\mathcal {F}}_{1}'|<{m_{k}-1 \choose k-1}+{m_{k-1}-1 \choose k-2}+\cdots +{m_{t}-1 \choose t-1}}$. Then by ${\displaystyle |{\mathcal {F}}|=|{\mathcal {F}}_{0}|+|{\mathcal {F}}_{1}'|}$, it holds that {\displaystyle {\begin{aligned}|{\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{aligned}}} so that, by the induction hypothesis, ${\displaystyle |\Delta {\mathcal {F}}_{0}|\geq {m_{k}-1 \choose k-1}+{m_{k-1}-1 \choose k-1}+\cdots +{m_{t}-1 \choose t-1}>|{\mathcal {F}}_{1}'|}$. On the other hand, by Lemma 2, ${\displaystyle |{\mathcal {F}}_{1}'|\geq |\Delta {\mathcal {F}}_{0}|}$. Thus ${\displaystyle |{\mathcal {F}}_{1}'|\geq |\Delta {\mathcal {F}}_{0}|>|{\mathcal {F}}_{1}'|}$, a contradiction.
${\displaystyle \square }$

Now we officially apply the induction. By Lemma 1,

${\displaystyle |\Delta {\mathcal {F}}|\geq |\Delta {\mathcal {F}}_{1}'|+|{\mathcal {F}}_{1}'|}$.

Note that ${\displaystyle {\mathcal {F}}_{1}'\subseteq {X \choose k-1}}$, and due to Lemma 3,

${\displaystyle |{\mathcal {F}}_{1}'|\geq {m_{k}-1 \choose k-1}+{m_{k-1}-1 \choose k-2}+\cdots +{m_{t}-1 \choose t-1}}$,

thus by the induction hypothesis,

${\displaystyle |\Delta {\mathcal {F}}_{1}'|\geq {m_{k}-1 \choose k-2}+{m_{k-1}-1 \choose k-3}+\cdots +{m_{t}-1 \choose t-2}}$.

Combining them together, we have

{\displaystyle {\begin{aligned}|\Delta {\mathcal {F}}|&\geq |\Delta {\mathcal {F}}_{1}'|+|{\mathcal {F}}_{1}'|\\&\geq {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{aligned}}}
${\displaystyle \square }$

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

 Definition The ${\displaystyle r}$-shadow of ${\displaystyle {\mathcal {F}}}$ is defined as ${\displaystyle \Delta _{r}{\mathcal {F}}=\left\{S\mid |S|=r{\text{ and }}\exists T\in {\mathcal {F}},S\subseteq T\right\}}$.

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

 Kruskal-Katona Theorem (general version) Let ${\displaystyle {\mathcal {F}}\subseteq {X \choose k}}$ with ${\displaystyle |{\mathcal {F}}|=m}$, and suppose that ${\displaystyle m={m_{k} \choose k}+{m_{k-1} \choose k-1}+\cdots +{m_{t} \choose t}}$ where ${\displaystyle m_{k}>m_{k-1}>\cdots >m_{t}\geq t\geq 1}$. Then for all ${\displaystyle r}$, ${\displaystyle 1\leq r\leq k}$, ${\displaystyle \left|\Delta _{r}{\mathcal {F}}\right|\geq {m_{k} \choose r}+{m_{k-1} \choose r-1}+\cdots +{m_{t} \choose t-k+r}}$.
Proof.
 Note that for ${\displaystyle {\mathcal {F}}\subseteq {X \choose k}}$, ${\displaystyle \Delta _{r}{\mathcal {F}}=\underbrace {\Delta \cdots \Delta } _{k-r}{\mathcal {F}}}$. The theorem follows by repeatedly applying the Kruskal-Katona theorem for ${\displaystyle \Delta {\mathcal {F}}}$.
${\displaystyle \square }$

 Erdős–Ko–Rado Theorem Let ${\displaystyle {\mathcal {F}}\subseteq {X \choose k}}$ where ${\displaystyle |X|=n}$ and ${\displaystyle n\geq 2k}$. If ${\displaystyle S\cap T\neq \emptyset }$ for any ${\displaystyle S,T\in {\mathcal {F}}}$, then ${\displaystyle |{\mathcal {F}}|\leq {n-1 \choose k-1}}$.
 (Daykin 1974, Clements 1976) By contradiction, suppose that ${\displaystyle |{\mathcal {F}}|>{n-1 \choose k-1}}$. We define the dual system ${\displaystyle {\mathcal {G}}=\{{\bar {S}}\mid S\in {\mathcal {F}}\}}$, where ${\displaystyle {\bar {S}}=X\setminus S}$. For any ${\displaystyle S,T\in {\mathcal {F}}}$, the condition ${\displaystyle S\cap T\neq \emptyset }$ is equivalent to ${\displaystyle S\not \subseteq {\bar {T}}}$, so ${\displaystyle {\mathcal {F}}}$ and ${\displaystyle \Delta _{k}{\mathcal {G}}}$ are disjoint, thus ${\displaystyle |{\mathcal {F}}|+|\Delta _{k}{\mathcal {G}}|\leq {n \choose k}}$. Clearly, ${\displaystyle {\mathcal {G}}\subseteq {X \choose n-k}}$ and ${\displaystyle |{\mathcal {G}}|=|{\mathcal {F}}|>{n-1 \choose k-1}={n-1 \choose n-k}}$. By the Kruskal-Katona theorem, ${\displaystyle |\Delta _{k}{\mathcal {G}}|\geq {n-1 \choose k}}$. ${\displaystyle |{\mathcal {F}}|+|\Delta _{k}{\mathcal {G}}|>{n-1 \choose k-1}+{n-1 \choose k}={n \choose k}}$, a contradiction.
${\displaystyle \square }$