Hypergraph containers
Numerous well-studied problems in combinatorics concern families of discrete structures that avoid certain forbidden configurations. For example, the celebrated theorem of Szemerédi states that every subset of {1, …, n} with no k-term arithmetic progression has o(n) elements; the archetypal problem studied in extremal graph theory, dating back to the work of Turán and Erdős and Stone, is the problem of characterising large graphs that avoid having some fixed graph H as a subgraph.
An important recent discovery in this area was that, perhaps surprisingly, it is beneficial to consider such problems in the abstract setting of independent sets in hypergraphs. This quickly leads one to ask the following general question: Given a finite set V and a hypergraph ℋ on V (whose edges we view as the forbidden configurations), what can be said about sets I ⊆ V that do not contain any member of ℋ? Such sets I are precisely the independent sets in ℋ.
Three natural questions that one usually asks for particular hypergraphs ℋ are:
- What are the largest independent sets in ℋ?
- What does a typical independent set in ℋ look like?
- What are the largest independent sets of ℋ among those contained in a random subset of V?
In this course, we shall present a general method that allows one to formalise and exploit the above connections between (i)--(iii) for many `interesting' ℋ. Our presentation will focus on applications of the method to `real-life' problems in areas such as graph theory, Ramsey theory, additive combinatorics, and discrete geometry.
Prerequisites
The course is intended to be elementary, but a general background in graph theory and discrete probability is expected. In particular, familiarity with the following results will be useful:
- Mantel’s theorem and Turán's theorem
- exponential tail bounds for binomial distributions (aka Chernoff bounds)
- Harris’s inequality
