Graphs and Matroids Seminar- Michelle Delcourt

Thursday, November 15, 2018 3:30 pm - 3:30 pm EST (GMT -05:00)

Title:  A Short Proof of the Containers Theorem for Hypergraphs

Speaker: Michelle Delcourt
Affiliation: University of Waterloo
Room: MC 6486

Abstract:  A modern trend in extremal combinatorics is extending classical results from the dense setting (e.g. Szemerédi's theorem) to the sparse random setting. More precisely, one shows that a property of a given "dense" structure is inherited by a randomly chosen "sparse" substructure. A recent breakthrough tool for proving such statements is the Balogh–Morris–Samotij and Saxton–Thomason hypergraph containers method, which bounds the number of independent sets in homogeneously dense finite hypergraphs, thus implying that a random sparse subset is not independent.  Here we present the first known deterministic proof of the containers theorem that is not algorithmic, i.e., it does not involve an iterative process.   This is joint work with Anton Bernshteyn, Henry Towsner, and Anush Tserunyan.