A short nonalgorithmic proof of the containers theorem for hypergraphs

Anton Bernshteyn, Michelle Delcourt, Henry Towsner, Anush Tserunyan

Research output: Contribution to journalArticle

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 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.

Original languageEnglish (US)
Pages (from-to)1739-1749
Number of pages11
JournalProceedings of the American Mathematical Society
Volume147
Issue number4
DOIs
StatePublished - Jan 1 2018

ASJC Scopus subject areas

  • Mathematics(all)
  • Applied Mathematics

Fingerprint Dive into the research topics of 'A short nonalgorithmic proof of the containers theorem for hypergraphs'. Together they form a unique fingerprint.

  • Cite this