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. References [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.

© Copyright 2017