Containers made easy

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. In a joint work with A. Bernshteyn, M. Delcourt, and H. Towsner, we give a new --- elementary and nonalgorithmic --- proof of the containers theorem for finite hypergraphs. Our proof is inspired by considering hyperfinite hypergraphs in the setting of nonstandard analysis, where there is a notion of dimension capturing the logarithmic rate of growth of finite sets. Applying this intuition in another setting with a notion of dimension, namely, algebraically closed fields, A. Bernshteyn, M. Delcourt, and I prove an analogous theorem for ``dense'' algebraically definable hypergraphs: any Zariski-generic low-dimensional subset of such hypergraphs is itself ``dense'' (in particular, not independent).

discrete mathematicscombinatoricslogic

Audience: researchers in the topic

Online logic seminar

Series comments: Description: Seminar on all areas of logic