Extremal set theory is a part of extremal combinatorics. The latter deals with the problems of the following type: given some class of objects, it asks for the largest/smallest (extremal) object in the class. Extremal set theory deals with such problems for a particular class of objects: collections (families) of sets.
This course has several parts: preliminaries, basics, advanced topics and research talks. We tried to structure the course in the way that, ultimately, the required minimal background for each part of the course, including the research part, is transparent. It is summarized in the graph that should be self-explanatory. The course is largely compiled from videos of different people (we are extremely grateful to all the lecturers for sharing their lectures on the internet!), and thus there may be some clash in notation etc. We try to make the transitions smooth by giving some extra texts before the videos.
Let us summarize some of the common notation for the course. $[n]$ stands for the set $\{1,\ldots, n\}$, $2^{X}$ or $P(X)$ stands for the power set of $X$, i.e., the collection of all subsets of $X$. ${[n]\choose k}$ or $[n]^{(k)}$ is the collection of all $k$-element subsets of $[n]$. A family is simply a collection of sets.
Preliminaries ꜜꜛ
You should be acquainted with induction, the basics of set theory and probability. You should know some basic facts about graphs and posets (such as Dilworth’s theorem). An introductory course on Discrete Mathematics should cover all these. The next video by Tim Gowers introduces two important ideas for the course (that are normally covered by the introductory DM course): the average of a random variable and double counting.
Basics ꜜꜛ
We are going to cover several basic extremal set theory theorems: The Erdos-Rado sunflower lemma, Erdos-Ko-Rado theorem, Sauer-Shelah lemma, Sperner’s theorem, Kruskal-Katona theorem, Katona’s $t$-intersecting theorem, oddtown theorem, Frankl-Wilson theorem. Along with this we will introduce three important methods in Extremal Set Theory: applications of double counting (or averaging), combinatorial operations and linear-algebraic (dimension) arguments.
The first result is the Erdos-Rado sunflower lemma, a very simple and powerful result. A sunflower with $r$ petals is a collection of $r$ distinct sets such that the intersection of any two is equal to the intersection of all of them. The lemma guarantees the existence of an $r$-sunflower in a sufficiently large family of $k$-element sets. The proof is a simple example of the use of induction:
Part 1: double counting ꜜꜛ
This part is devoted to the idea that, in order to prove a theorem about a complicated structure, it is sometimes enough to prove a statement about a simple substructure and then average it over different choices of that substructure.
Summary: the Erdos-Ko-Rado theorem, Sperner theorem, Bollobas’ set-pair inequality.
A family $\mathcal F$ is intersecting if $F_1\cap F_2\ne \emptyset$ for any two sets from $\mathcal F$. The Erdos-Ko-Rado theorem gives a sharp upper bound on the size of an intersecting $\mathcal F\subset {[n]\choose k}$.
The proof we are going to learn is via Katona’s circle method. Here is the video by Tim Gowers:
Alternatively, here is the video by Gyula Katona himself: the first 10 minutes of the video
A family $\mathcal F$ is an antichain if there are no $F_1,F_2\in \mathcal F$ such that $F_1\subsetneq F_2$. Sperner's theorem gives the largest size of an antichain in $2^{[n]}$.
We are going to see the proof of Sperner’s theorem using chains. Here is the video by Tim Gowers:
Alternatively, here is the video by Gyula Katona.
The statement is on minute 6. He gives several proofs of Sperner’s theorem, the first one [minutes 8-32] is based on biregular bipartite graphs and uses the same ideas as shown at the end of the Tim Gowers video on double counting in the Preliminaries section. The second proof is using chains [minutes 32-42].
Bollobás’ set-pair inequality is a very useful generalization of Sperner's theorem. Take a look at pages 4-5 of the book by Gerbner and Patkós “Extremal Finite Set Theory”.
Part 2: 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.
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
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.
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”.
Part 3: Introduction to linear-algebraic method ꜜꜛ
The theme of this section is as follows: given a family with certain restrictions on pairwise intersections, we associate polynomials with each set and show that they are linearly independent. We then bound the size of the family by the dimension of the space of the polynomials.
Summary: the oddtown theorem, the Frankl-Wilson theorem.
Take a family such that the sizes of all sets in the family are odd/even and their intersections are odd/even. How big can it be? The answer is dramatically different depending on the choice of the conditions we make. Here is the video by Tim Gowers:
Take a prime p and a family of 2p-element sets in [4p] with no two sets intersecting in exactly p elements. How big can this family be? The upper bound is given by the Frankl-Wilson theorem, which is very useful in several problems in combinatorial geometry. Here is the video by Tim Gowers: