A short nonalgorithmic proof of the containers theorem for hypergraphs

Bernshteyn, Anton; Delcourt, Michelle; Towsner, Henry; Tserunyan, Anush

doi:10.1090/proc/14368

A short nonalgorithmic proof of the containers theorem for hypergraphs
HTML articles powered by AMS MathViewer

by Anton Bernshteyn, Michelle Delcourt, Henry Towsner and Anush Tserunyan PDF

Proc. Amer. Math. Soc. 147 (2019), 1739-1749

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

József Balogh, Robert Morris, and Wojciech Samotij, Independent sets in hypergraphs, J. Amer. Math. Soc. 28 (2015), no. 3, 669–709. MR 3327533, DOI 10.1090/S0894-0347-2014-00816-X
J. Balogh, R. Morris, and W. Samotij, The method of hypergraph containers, preprint, https://arxiv.org/abs/1801.04584
David Conlon, Combinatorial theorems relative to a random set, Proceedings of the International Congress of Mathematicians—Seoul 2014. Vol. IV, Kyung Moon Sa, Seoul, 2014, pp. 303–327. MR 3727614
D. Conlon and W. T. Gowers, Combinatorial theorems in sparse random sets, Ann. of Math. (2) 184 (2016), no. 2, 367–454. MR 3548529, DOI 10.4007/annals.2016.184.2.2
P. Erdős, P. Frankl, and V. Rödl, The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent, Graphs Combin. 2 (1986), no. 2, 113–121. MR 932119, DOI 10.1007/BF01788085
M. Di Nasso, I. Goldbring, and M. Lupini, Nonstandard Methods in Ramsey Theory and Combinatorial Number Theory, draft, https://arxiv.org/abs/1709.04076
D. García, A note on pseudofinite dimensions and forking, note, https://arxiv.org/abs/1402.5212
Robert Goldblatt, Lectures on the hyperreals, Graduate Texts in Mathematics, vol. 188, Springer-Verlag, New York, 1998. An introduction to nonstandard analysis. MR 1643950, DOI 10.1007/978-1-4612-0615-6
Ehud Hrushovski, Stable group theory and approximate subgroups, J. Amer. Math. Soc. 25 (2012), no. 1, 189–243. MR 2833482, DOI 10.1090/S0894-0347-2011-00708-X
Ehud Hrushovski, On pseudo-finite dimensions, Notre Dame J. Form. Log. 54 (2013), no. 3-4, 463–495. MR 3091666, DOI 10.1215/00294527-2143952
Ehud Hrushovski and Frank Wagner, Counting and dimensions, Model theory with applications to algebra and analysis. Vol. 2, London Math. Soc. Lecture Note Ser., vol. 350, Cambridge Univ. Press, Cambridge, 2008, pp. 161–176. MR 2436141, DOI 10.1017/CBO9780511735219.005
Tomasz Łuczak, On triangle-free random graphs, Random Structures Algorithms 16 (2000), no. 3, 260–276. MR 1749289, DOI 10.1002/(SICI)1098-2418(200005)16:3<260::AID-RSA3>3.3.CO;2-H
Vojtěch Rödl and Mathias Schacht, Extremal results in random graphs, Erdös centennial, Bolyai Soc. Math. Stud., vol. 25, János Bolyai Math. Soc., Budapest, 2013, pp. 535–583. MR 3203611, DOI 10.1007/978-3-642-39286-3_{2}0
David Saxton and Andrew Thomason, Hypergraph containers, Invent. Math. 201 (2015), no. 3, 925–992. MR 3385638, DOI 10.1007/s00222-014-0562-8
David Saxton and Andrew Thomason, Simple containers for simple hypergraphs, Combin. Probab. Comput. 25 (2016), no. 3, 448–459. MR 3482665, DOI 10.1017/S096354831500022X
Mathias Schacht, Extremal results for random discrete structures, Ann. of Math. (2) 184 (2016), no. 2, 333–365. MR 3548528, DOI 10.4007/annals.2016.184.2.1
E. Szemerédi, On sets of integers containing no $k$ elements in arithmetic progression, Acta Arith. 27 (1975), 199–245. MR 369312, DOI 10.4064/aa-27-1-199-245