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 -