A short nonalgorithmic proof of the containers theorem for hypergraphs

Abstract:

Recently the breakthrough method of hypergraph containers, developed independently by Balogh, Morris, and Samotij [J. Amer. Math. Soc. 28 (2015), pp. 669–709] as well as Saxton and Thomason [Invent. Math. 201 (2015), pp. 925–992], has been used to study sparse random analogs of a variety of classical problems from combinatorics and number theory. The previously known proofs of the containers theorem use the so-called scythe algorithm—an iterative procedure that runs through the vertices of the hypergraph. (Saxton and Thomason [Combin. Probab. Comput. 25 (2016), pp. 448–459] have also proposed an alternative, randomized construction in the case of simple hypergraphs.) 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. Our proof is less than four pages long while being entirely self-contained and conceptually transparent. Although our proof is completely elementary, it was inspired by considering hypergraphs in the setting of nonstandard analysis, where there is a notion of dimension capturing the logarithmic rate of growth of finite sets. Before presenting the proof in full detail, we include a one page informal outline that refers to this notion of dimension and summarizes the essence of the argument.