Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

   
 
 

 

A short nonalgorithmic proof of the containers theorem for hypergraphs


Authors: Anton Bernshteyn, Michelle Delcourt, Henry Towsner and Anush Tserunyan
Journal: Proc. Amer. Math. Soc. 147 (2019), 1739-1749
MSC (2010): Primary 03C20, 05C35, 05C65, 05C69
DOI: https://doi.org/10.1090/proc/14368
Published electronically: January 9, 2019
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 03C20, 05C35, 05C65, 05C69

Retrieve articles in all journals with MSC (2010): 03C20, 05C35, 05C65, 05C69


Additional Information

Anton Bernshteyn
Affiliation: Department of Mathematics, University of Illinois at Urbana-Champaign, Urbana, Illinois 61801
Email: bernsht2@illinois.edu

Michelle Delcourt
Affiliation: School of Mathematics, University of Birmingham, Birmingham B15 2TS, United Kingdom
Email: m.delcourt@bham.ac.uk

Henry Towsner
Affiliation: Department of Mathematics, University of Pennsylvania, Philadelphia, Pennsylvania 19104
Email: htowsner@math.upenn.edu

Anush Tserunyan
Affiliation: Department of Mathematics, University of Illinois at Urbana-Champaign, Urbana, Illinois 61801
Email: anush@illinois.edu

DOI: https://doi.org/10.1090/proc/14368
Received by editor(s): January 22, 2018
Received by editor(s) in revised form: January 24, 2018, and August 30, 2018
Published electronically: January 9, 2019
Additional Notes: The second author’s research was partially supported by EPSRC grant EP/P009913/1 and NSF Graduate Research Fellowship DGE 1144245.
The third author’s research was partially supported by NSF Grant DMS-1600263.
The fourth author’s research was partially supported by NSF Grant DMS-1501036.
Communicated by: Patricia L. Hersh
Article copyright: © Copyright 2019 by the authors