A short nonalgorithmic proof of the containers theorem for hypergraphs. Bernshteyn, A., Delcourt, M., Towsner, H., & Tserunyan, A. *Proc. Amer. Math. Soc*, 2019. Arxiv Journal doi abstract bibtex 22 downloads Recently the breakthrough method of hypergraph containers, developed independently by Balogh, Morris, and Samotij as well as Saxton and Thomason, has been used to study sparse random analogues of a variety of classical problems from combinatorics and number theory. In this paper, we give the first known proof of this theorem that does not involve an inductive construction (i.e., the so-called scythe algorithm). This proof is less than 4 pages long while being entirely self-contained. 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.

@article{1801.07186,
author = {{Bernshteyn}, A. and {Delcourt}, M. and {Towsner}, H. and {Tserunyan}, A.
},
title = "{A short nonalgorithmic proof of the containers theorem for hypergraphs}",
vol=147,
pages={1739--1749},
year = 2019,
urlarxiv = {https://arxiv.org/abs/1801.07186},
urljournal={https://www.ams.org/journals/proc/0000-000-00/S0002-9939-2019-14368-9/},
journal = {Proc. Amer. Math. Soc},
doi = {10.1090/proc/14368},
abstract={Recently the breakthrough method of hypergraph containers, developed independently by Balogh, Morris, and Samotij as well as Saxton and Thomason, has been used to study sparse random analogues of a variety of classical problems from combinatorics and number theory. In this paper, we give the first known proof of this theorem that does not involve an inductive construction (i.e., the so-called scythe algorithm). This proof is less than 4 pages long while being entirely self-contained. 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.
}
}

Downloads: 22

{"_id":"rMPWJkGb4iw2Nbccs","bibbaseid":"bernshteyn-delcourt-towsner-tserunyan-ashortnonalgorithmicproofofthecontainerstheoremforhypergraphs-2019","downloads":22,"creationDate":"2019-02-08T16:54:49.302Z","title":"A short nonalgorithmic proof of the containers theorem for hypergraphs","author_short":["Bernshteyn, A.","Delcourt, M.","Towsner, H.","Tserunyan, A."],"year":2019,"bibtype":"article","biburl":"www.sas.upenn.edu/~htowsner/papers.bib","bibdata":{"bibtype":"article","type":"article","author":[{"propositions":[],"lastnames":["Bernshteyn"],"firstnames":["A."],"suffixes":[]},{"propositions":[],"lastnames":["Delcourt"],"firstnames":["M."],"suffixes":[]},{"propositions":[],"lastnames":["Towsner"],"firstnames":["H."],"suffixes":[]},{"propositions":[],"lastnames":["Tserunyan"],"firstnames":["A."],"suffixes":[]}],"title":"A short nonalgorithmic proof of the containers theorem for hypergraphs","vol":"147","pages":"1739–1749","year":"2019","urlarxiv":"https://arxiv.org/abs/1801.07186","urljournal":"https://www.ams.org/journals/proc/0000-000-00/S0002-9939-2019-14368-9/","journal":"Proc. Amer. Math. Soc","doi":"10.1090/proc/14368","abstract":"Recently the breakthrough method of hypergraph containers, developed independently by Balogh, Morris, and Samotij as well as Saxton and Thomason, has been used to study sparse random analogues of a variety of classical problems from combinatorics and number theory. In this paper, we give the first known proof of this theorem that does not involve an inductive construction (i.e., the so-called scythe algorithm). This proof is less than 4 pages long while being entirely self-contained. 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. ","bibtex":"@article{1801.07186,\n author = {{Bernshteyn}, A. and {Delcourt}, M. and {Towsner}, H. and {Tserunyan}, A.\n\t},\n title = \"{A short nonalgorithmic proof of the containers theorem for hypergraphs}\",\nvol=147,\npages={1739--1749},\n year = 2019,\n urlarxiv = {https://arxiv.org/abs/1801.07186},\n urljournal={https://www.ams.org/journals/proc/0000-000-00/S0002-9939-2019-14368-9/},\n journal = {Proc. Amer. Math. Soc},\n doi = {10.1090/proc/14368},\nabstract={Recently the breakthrough method of hypergraph containers, developed independently by Balogh, Morris, and Samotij as well as Saxton and Thomason, has been used to study sparse random analogues of a variety of classical problems from combinatorics and number theory. In this paper, we give the first known proof of this theorem that does not involve an inductive construction (i.e., the so-called scythe algorithm). This proof is less than 4 pages long while being entirely self-contained. 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.\n}\n}\n\n\n","author_short":["Bernshteyn, A.","Delcourt, M.","Towsner, H.","Tserunyan, A."],"key":"1801.07186","id":"1801.07186","bibbaseid":"bernshteyn-delcourt-towsner-tserunyan-ashortnonalgorithmicproofofthecontainerstheoremforhypergraphs-2019","role":"author","urls":{"Arxiv":"https://arxiv.org/abs/1801.07186","Journal":"https://www.ams.org/journals/proc/0000-000-00/S0002-9939-2019-14368-9/"},"metadata":{"authorlinks":{"towsner, h":"https://www.sas.upenn.edu/~htowsner/index.html"}},"downloads":22,"html":""},"search_terms":["short","nonalgorithmic","proof","containers","theorem","hypergraphs","bernshteyn","delcourt","towsner","tserunyan"],"keywords":[],"authorIDs":["3GEPwq9joMrcxxoCw","4KQet7uefuvLzwtpx","545832462abc8e9f37000b09","5c8vhjzWNNjGW4qbh","5decfea43d02efdf010000be","5def8c8545114dde01000167","5df216ace4cb4ede0100016b","5e04f7d6fff612df01000139","5e07fc92cdee3adf0100003b","5e0b8c33ca6111df010000a2","5e0fd5b12cfae9df010000b2","5e10e8e545c12cde01000086","5e15529bedfb1ede01000156","5e1ae0065f3d2cdf01000075","5e25e33da6f19fde010000f0","5e2ecddbc2015cde01000106","5e2f2e7378a7cedf01000043","5e2f7d669ca24fdf010001e9","5e31874200e4e5de010000f3","5e349b4753b794de01000107","5e3871a21f8af9e0010000f6","5e3d9a82f33211df01000085","5e3daa13f33211df01000192","5e405ccaaeea22df0100009b","5e442d87e5a34dde010000ac","5e4a4b925675c1de01000107","5e51554afe5af9df01000104","5e52ae476a3abede0100003e","5e599979ad6c7fde0100004a","5e5c8dfa9933dade01000017","5e5d5d37ad47bcde010000c0","5e5e8a77c0a53dde01000054","5e5e9e03c0a53dde0100025f","5e64727de1ac00de010000d6","8eyEAbrHsTiQjrh7m","9xwKHbohnMHpGd326","AKhMye69vFo9ZBkJn","B8ktHCTYohgyN3zHd","BeL58hABvbynGFvkM","E6dySSeKcY8eAMMJB","EHJuZpHSt5bw4erqn","EjhY4z5ziCGtFZAAp","Fr8xk6h7QLy2uc6qT","HGCndpBQapLkeXcCv","JXPiBhJhKZpboe3cv","KYQ2gtq5nH4r2yEXs","M5pdPBbKqC9YYHd6n","PKNH7m7rTTAWiLt3x","Pz5HyZqksZg56dyuD","QJDeWCekzoGrAH7hG","QWy8CzoFcY4jkh9XS","RWoRfxCmeqb6fsA7N","RiWhh5sCAejRxYRtr","TdZKmjjXfpX5riMhc","W8K2TwaE7YMfqQquc","W9X6jnrT5WndXxz4f","WJ4bEb9E3XqnkvyCX","XMaQnCeR8pCaxKwS6","ZB6i2RZxTFGTnNJcr","ZfXCGDcjZMeE4QSqP","b9AcCuxsqzpiCMFsG","cNR3H4e3QEnD3WkbJ","cnQY9tt7BQH92KkyP","fDCSEz7FfSCxERX9L","fkakjW7HDbgrSiTnc","g2bZv9uHbxMAPTro2","mgLyDAsFS9g7HNyuT","n6SFWyWp7WHG5YnrG","nDtKTAspawBCun8X8","nJTiiRRLbohMDGYgA","nvTYkDHXvRYJbiLqm","o6p92SSgdiePc5yu8","oNpdLEjNerjoioXTr","qTYgvoePYaSXGnmPe","t9d9TPHkaTGkNr5RP","tYHK4CxbC8KJ8CgMF","vymEvveSkq34uS28E","wm9ugGRCbkcFjNxF5","xJZc77uii7zQDbato","xvWPite86SqosFSo5"],"dataSources":["6NR8bS3FWz4thtH6K","HbyKaYarx2Kg7vovB"]}