Combinatorial operations
In this part, we will introduce two combinatorial operations: shifting and squashing (downward shifting). When applied to a family, they preserve the size of the family, as well as some of the properties of the family that we may be interested in. As a result, in many cases it is sufficient to prove extremal results for families that have a certain structure, and this structure often simplifies the analysis.
Summary: the Erdos-Ko-Rado theorem, Kruskal-Katona theorem, Sauer-Shelah-Vapnik-Chervonenkis lemma.
For bigger picture see Extremal Set Theory Course
We start with another proof of the Erdos-Ko-Rado theorem. Here is a video by Gyula Katona [the k-uniform version starting from minute 11]:
Alternatively, here is a shorter video by Andrey Kupavskii:
It relies on the properties of shifting and reduction of the problem to the case of shifted families. Let us give a proof of that below.
First, we define a `$j$ to $i$ shift' $S_{i\leftarrow j}$ for a set $A$. We have $S_{i\leftarrow j}(A) = A$ if $A\cap \{i,j\}\ne \{j\}$ and $S_{i\leftarrow j}(A) = A\setminus \{j\} \cup \{i\}$ if $A\cap \{i,j\} = \{j\}$. Informally, we replace $j$ by $i$ in $A$ whenever only $j$ is present. Next, we define a shift for a family $\mathcal F$: $$S_{i\leftarrow j}(\mathcal F) = \{S_{i\leftarrow j}(A):A\in \mathcal F\}\cup \{A: A,S_{i\leftarrow j}(A)\in \mathcal F\}.$$ Informally, we replace $A$ by its shift if it does not cause collisions between sets of $\mathcal F$. If it would, we leave $A$ intact. Note that $|S_{i\leftarrow j}(\mathcal F) = |\mathcal F|$.
The following two lemmas summarize the properties of shifting that we need. The first lemma is in a slightly more general form than we need. Let us call a family $t$-intersecting if any two sets from the family intersect in at least $t$ elements.
Lemma. If a family $\mathcal F$ is $t$-intersecting then the family $S_{i\leftarrow j}(\mathcal F)$ is intersecting as well.
Proof. In the proof, we show that for any $A', B'\in S_{i\leftarrow j}(\mathcal F)$ the intersection of $A'$ and $B'$ is at least as large as intersection of some pair of sets from $\mathcal F$, and thus if $\mathcal F$ was $t$-intersecting, then so is $S_{i\leftarrow j}(\mathcal F)$.
Take any two sets $A',B'\in S_{i\leftarrow j}(\mathcal F)$. Then, by the definition of shifts, there are two sets $A,B\in \mathcal F$ such that $A'$ is either equal to $A$ or to $A\setminus \{j\}\cup \{i\}$ (and $A\cap \{i,j\} = \{j\}$ in the latter case) and, similarly, $B'$ is either equal to $B$ or $B\setminus \{j\}\cup \{i\}$ (and $B\cap \{i,j\} = \{j\}$ in the latter case). It is clear that $A'\cap B' = A\cap B$ unless exactly one of $A=A'$ or $B= B'$ holds. We may without loss of generality assume that $A = A'$ and $B' = B\setminus \{j\} \cup \{i\}$.
Further, we observe that if $|A\cap \{i,j\}|=0$ or $2$ then, again, $A'\cap B'= A\cap B$. Moreover, if $i\in A$ then $|B'\cap A'|\ge|B\cap A|$. Therefore, $A\cap \{i,j\} = \{j\}$. By the definition of a $j$ to $i$ shift for a family, we note that we could leave $A$ intact in this case only if $S_{i\leftarrow j}(A)$ belonged to $\mathcal F$. But then $|A'\cap B'| = |S_{i\leftarrow j}(A)\cap B|$, where both sets in the latter intersection are from $\mathcal F$.
□
We say that a family $\mathcal F$ is shifted (to the left) if $S_{i\leftarrow j}(\mathcal F) =\mathcal F$ for any $i < j$. (We can define being shifted to the right analogously, just replacing `$i < j$' with `$i > j$'. However, in this course we will almost exclusively use shiftedness to the left and will typically omit `to the left' for brevity. The same property is sometimes called `left-compressed'.) Note (verify!) that this definition coincides with the definition from the video by Andrey Kupavskii above.
Lemma. Any finite family can be made shifted after a finite number of applications of $j$ to $i$ shifts with $i < j$.
Proof. In order to show that, we find a simple integer invariant of a family that decreases each time we apply a shift (and its application is non-trivial). One possible invariant is as follows: $\sum_{A\in\mathcal F}\sum_{i\in A} i$. Clearly, this sum is finite and nonnegative for any finite family. At the same time, it strictly decreases each time an $j$ to $i$ shift with $i < j$ actually changes the family. Thus, after finitely many steps we arrive at a family in which the sum cannot be decreased any more, and that is therefore shifted.
□
Given a family $\mathcal F$ of $k$-element sets, its shadow $\partial \mathcal F$ is the collection of all $(k-1)$-element sets that are contained in some $F$, $F\in \mathcal F$. Formally, $$\partial \mathcal F = \bigcup_{F\in \mathcal F} {F\choose k-1}.$$ A simple relation between $|\mathcal F|$ and $|\partial \mathcal F|$ for a family $\mathcal F\subset {[n]\choose k}$ can be obtained using double counting (similar to that from the double counting video of Tim Gowers). The Kruskal-Katona theorem gives a best possible relation between these two quantities.
Below, we verify that shifting does not increase the size of the shadow. More precisely, we prove the following lemma.
Lemma. For any family $\mathcal F$ and integers $i,j$, we have $\partial \big(S_{i\leftarrow j}(\mathcal F)\big)\subset S_{i\leftarrow j}(\partial \mathcal F)$.
The proof of this lemma is a rather tedious case analysis, and we present it for completeness, as a yet another illustration on how to verify that shiftedness preserves different properties.
Proof. Take $A\in \partial \big(S_{i\leftarrow j}(\mathcal F)\big)$. First note that there is $B\in S_{i\leftarrow j}(\mathcal F)$ such that $A\subset B$. Next, there is $B'\in \mathcal F$ such that $S_{i\leftarrow j}(B') \in \{B, S_{i\leftarrow j}(B)\}$.
If $j\notin B'$ then $B = B'$ and so $A\in \partial (\mathcal F)$. Moreover, $j\notin A$, and $A = S_{i\leftarrow j}(A)$, which implies $A\in S_{i\leftarrow j}(\partial \mathcal F)$.
If $\{i,j\} \subset B'$ then $B = B'$ and $A, S_{i\leftarrow j}(A) \subset B$. This again implies $A\in S_{i\leftarrow j}(\partial \mathcal F)$.
Assume that $B'\cap \{i,j\} = \{j\}$ and $B= B'$. Then $S_{i\leftarrow j}(B)\in \mathcal F$, which means that $A, S_{i\leftarrow j}(A)\in\partial \mathcal F$ and thus $A\in S_{i\leftarrow j}(\partial \mathcal F)$.
Finally, assume that $B'\cap \{i,j\} = \{j\}$ and $B= S_{i\leftarrow j}(B')$. If $A\cap \{i,j\} = \emptyset$ then clearly $A\subset B$, $A\in \partial\mathcal F$ and $A\in S_{i\leftarrow j}(\partial \mathcal F)$. If $A\cap \{i,j\} = \{i\}$ then $A\setminus\{i\}\cup\{j\}\subset B'$, $(A\setminus\{i\})\cup\{j\}\in \partial\mathcal F$, and $S_{i\leftarrow j}\big((A\setminus\{i\})\cup\{j\}\big)\in S_{i\leftarrow j}(\partial \mathcal F)$. But $S_{i\leftarrow j}\big((A\setminus\{i\})\cup\{j\}\big) = A$.
□
Here is a proof of the Kruskal-Katona theorem using shifting and induction:
For more details, See Theorem 2.14 and Proposition 2.10, as well as Chapter 6, of the book by Frankl and Tokushige “Extremal Problems for Finite Sets”. Note that the authors use $\sigma$ instead of $\partial$ to denote shadows.
For a family $\mathcal F$ and a set $X$, let us define the trace $\mathcal F|_X:=\{F\cap X: F\in \mathcal F\}.$ We say that $X$ is shattered by $\mathcal F$ if $\mathcal F|_X = 2^X$. The VC-dimension of $\mathcal F$, denoted by ${\rm VC}(\mathcal F)$, is the size of the largest set shattered by $\mathcal F$. This is an extremely important complexity characteristic of a family that is useful for machine learning, computational geometry, graph theory and model theory, among other things. One of the key results in this respect is the Sauer-Shelah-Vapnik-Chervonenkis lemma that gives a sharp bound for $|\mathcal F|$ from above for $\mathcal F\subset 2^{[n]}$ with ${\rm VC}(\mathcal F) \le d$.
Here is a proof of the Sauer-Shelah-Vapnik-Chervonenkis lemma using a certain combinatorial operation, which we call squashing. The proof follows the same pattern: we define a certain class of combinatorial operations and then reduce the proof to the case when the family is invariant under such operations. Once this is done, the rest is almost trivial.
Alternatively, see Theorem 3.1 of the book by Frankl and Tokushige “Extremal Problems for Finite Sets”.