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
Additional Information
- Anton Bernshteyn
- Affiliation: Department of Mathematics, University of Illinois at Urbana-Champaign, Urbana, Illinois 61801
- MR Author ID: 1104079
- Email: bernsht2@illinois.edu
- Michelle Delcourt
- Affiliation: School of Mathematics, University of Birmingham, Birmingham B15 2TS, United Kingdom
- MR Author ID: 923919
- Email: m.delcourt@bham.ac.uk
- Henry Towsner
- Affiliation: Department of Mathematics, University of Pennsylvania, Philadelphia, Pennsylvania 19104
- MR Author ID: 745396
- Email: htowsner@math.upenn.edu
- Anush Tserunyan
- Affiliation: Department of Mathematics, University of Illinois at Urbana-Champaign, Urbana, Illinois 61801
- MR Author ID: 853942
- Email: anush@illinois.edu
- 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
- © Copyright 2019 by the authors
- Journal: Proc. Amer. Math. Soc. 147 (2019), 1739-1749
- MSC (2010): Primary 03C20, 05C35, 05C65, 05C69
- DOI: https://doi.org/10.1090/proc/14368
- MathSciNet review: 3910438