Computer Science/Discrete Mathematics Seminar II

The method of hypergraph containers is a widely-applicable technique in probabilistic combinatorics. The method enables one to gain control over the independent sets of many `interesting' hypergraphs by exploiting the fact that these sets exhibit a certain subtle clustering phenomenon. Since many problems studied in extremal and probabilistic combinatorics, Ramsey theory, and discrete geometry can be (naturally) phrased in terms of independent sets in auxiliary hypergraphs, good control over these sets has many `practical' consequences.

In the first part of this talk, I will provide a gentle introduction to the method, guided and motivated by the following elementary problem in Ramsey theory: Does there exist a graph G without a complete subgraph on four vertices that cannot be partitioned into two triangle-free graphs?

The heart of the method is a hypergraph container lemma (HCL) – a formal statement that quantifies the aforementioned notion of clustering. In the second part of this talk, I will state and discuss several HCLs and, if time permits, sketch a (short) proof of one of them (found recently in collaboration with Marcelo Campos).