Simons Collaboration on Algorithms and Geometry Monthly Meeting, December 2020

 
The method of hypergraph containers – Jozsef Balogh and Wojciech Samotij

We will give a gentle introduction to a recently-developed technique, the method of hypergraph containers, for bounding the number (and controlling the typical structure) of finite objects satisfying a family of local constraints. This technique exploits a subtle clustering phenomenon exhibited by the independent sets of uniform hypergraphs whose edges are sufficiently evenly distributed; more precisely, it provides a relatively small family of ‘containers’ for the independent sets, each of which is ‘nearly’ independent (it contains very few edges).

In Lecture 1, we will attempt to convey a general, high-level overview of the method, via applications in extremal graph theory.
We will discuss some history and motivation, and present an informal statement of the hypergraph container lemma.

In Lecture 2, we will present a few elementary but illustrative applications in areas such as additive combinatorics and discrete geometry.

In Lecture 3, we will present some less straightforward applications of the method, including problems with many colours (such as Ramsey properties of random structures), which are not immediately representable as questions about independent sets in hypergraphs.

In Lecture 4, we will present a formal statement of the hypergraph container lemma and sketch its proof.