Hypergraph containers Wojciech Samotij

Hypergraph containers
Wojciech Samotij
(Tel Aviv University)
A great many of the central questions in combinatorics fall into the following
general framework: Given a finite set V and a collection H ⊆ P(V ) of forbidden
structures, what can be said about sets I ⊆ V that do not contain any member
of H? Such sets I are called independent in H. For example, the celebrated
theorem of Szemer´edi states that if V = {1, . . . , n} and H is the collection
of k-term arithmetic progressions in {1, . . . , n}, then every independent set has
o(n) elements. The archetypal problem studied in extremal graph theory, dating
back to the work of Tur´
an and Erd˝os and Stone, is the problem of characterizing
independent sets when V is the edge set of the complete graph on n vertices
and H is the collection of copies of some fixed graph H in Kn .
Two natural questions that one might ask about such H are:
(i) What are the largest independent sets in H?
(ii) What does a typical independent set in H look like?
It turns out that for a large class of H, problems (i) and (ii) are very closely
related. In particular, a typical independent set is ‘close’ to a typical subset of
some largest independent set.
In this course, we shall present a general method, developed by Balogh, Morris,
and Samotij [1] and, independently, by Saxton and Thomason [2] that allows
one to formalize and exploit the above connection between (i) and (ii) for many
‘interesting’ H. Our presentation will focus on applications of the method to
‘real life’ problems.
This course is intended to be introductory and no background in extremal graph
theory is required.
[1] Balogh, J., Morris, R., and Samotij, W. Independent sets in hypergraphs. to appear in Journal of the American Mathematical Society.
[2] Saxton, D., and Thomason, A. Hypergraph containers. submitted.