TY - JOUR

T1 - A short nonalgorithmic proof of the containers theorem for hypergraphs

AU - Bernshteyn, Anton

AU - Delcourt, Michelle

AU - Towsner, Henry

AU - Tserunyan, Anush

N1 - Publisher Copyright:
© 2019 American Mathematical Society.

PY - 2018

Y1 - 2018

N2 - 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 hyper-graphs.) 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.

AB - 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 hyper-graphs.) 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.

UR - http://www.scopus.com/inward/record.url?scp=85062024040&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85062024040&partnerID=8YFLogxK

U2 - 10.1090/proc/14368

DO - 10.1090/proc/14368

M3 - Article

AN - SCOPUS:85062024040

SN - 0002-9939

VL - 147

SP - 1739

EP - 1749

JO - Proceedings of the American Mathematical Society

JF - Proceedings of the American Mathematical Society

IS - 4

ER -