Extremal Set Theory
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: