The limit in the $(k+2, k)$-problem of Brown, Erdős and Sós exists for all $k\geq 2$
HTML articles powered by AMS MathViewer
- by Michelle Delcourt and Luke Postle;
- Proc. Amer. Math. Soc. 152 (2024), 1881-1891
- DOI: https://doi.org/10.1090/proc/16668
- Published electronically: March 1, 2024
- HTML | PDF | Request permission
Abstract:
Let $f^{(r)}(n;s,k)$ be the maximum number of edges of an $r$-uniform hypergraph on $n$ vertices not containing a subgraph with $k$ edges and at most $s$ vertices. In 1973, Brown, Erdős and Sós conjectured that the limit \begin{equation*} \lim _{n\to \infty } n^{-2} f^{(3)}(n;k+2,k) \end{equation*} exists for all positive integers $k\ge 2$. They proved this for $k=2$. In 2019, Glock proved this for $k=3$ and determined the limit. Quite recently, Glock, Joos, Kim, Kühn, Lichev and Pikhurko proved this for $k=4$ and determined the limit; we combine their work with a new reduction to fully resolve the conjecture by proving that indeed the limit exists for all positive integers $k\ge 2$.References
- Tom Bohman and Lutz Warnke, Large girth approximate Steiner triple systems, J. Lond. Math. Soc. (2) 100 (2019), no. 3, 895–913. MR 4048725, DOI 10.1112/jlms.12242
- W. G. Brown, P. Erdős, and V. T. Sós, Some extremal problems on $r$-graphs, New directions in the theory of graphs (Proc. Third Ann Arbor Conf., Univ. Michigan, Ann Arbor, Mich., 1971) Academic Press, New York-London, 1973, pp. 53–63. MR 351888
- Michelle Delcourt and Luke Postle, Finding an almost perfect matching in a hypergraph avoiding forbidden submatchings, arXiv:2204.08981, 2022.
- Paul Erdős, Problems and results in combinatorial analysis, Colloquio Internazionale sulle Teorie Combinatorie (Roma, 1973) Accad. Naz. Lincei, Rome, 1976, pp. 3–17 (English, with Italian summary). MR 465878
- Stefan Glock, Triple systems with no three triples spanning at most five points, Bull. Lond. Math. Soc. 51 (2019), no. 2, 230–236. MR 3937584, DOI 10.1112/blms.12224
- Stefan Glock, Felix Joos, Jaehoon Kim, Marcus Kühn, and Lyuben Lichev, Conflict-free hypergraph matchings, Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, PA, 2023, pp. 2991–3005. MR 4538067, DOI 10.1137/1.9781611977554.ch115
- Stefan Glock, Felix Joos, Jaehoon Kim, Marcus Kahn, Lyuben Lichev, and Oleg Pikhurko, On the (6,4)-problem of Brown, Erdős, and Sós, Proc. Amer. Math. Soc., To appear, arXiv:2209.14177, 2022.
- Stefan Glock, Daniela Kühn, Allan Lo, and Deryk Osthus, On a conjecture of Erdős on locally sparse Steiner triple systems, Combinatorica 40 (2020), no. 3, 363–403. MR 4121151, DOI 10.1007/s00493-019-4084-2
- Stefan Glock, Daniela Kühn, Allan Lo, and Deryk Osthus, The existence of designs via iterative absorption: hypergraph $F$-designs for arbitrary $F$, Mem. Amer. Math. Soc. 284 (2023), no. 1406, v+131. MR 4572074, DOI 10.1090/memo/1406
- Peter Keevash, The existence of designs, Preprint, arXiv:1401.3665, 2014.
- Peter Keevash and Jason Long, The Brown-Erdős-Sós conjecture for hypergraphs of large uniformity, arXiv:2007.14824, 2020.
- T. P. Kirkman, On a problem in combinatorics, Camb. Dublin Math. J. 2 (1847), 191–204.
- Matthew Kwan, Ashwin Sah, Mehtaab Sawhney, and Michael Simkin, High-girth Steiner triple systems, Preprint, arXiv:2201.04554, 2022.
- Hanno Lefmann, Kevin T. Phelps, and Vojtěch Rödl, Extremal problems for triple systems, J. Combin. Des. 1 (1993), no. 5, 379–394. MR 1303951, DOI 10.1002/jcd.3180010506
- Chong Shangguan, Degenerate Turán densities of sparse hypergraphs II: a solution to the Brown-Erdős-Sós problem for every uniformity, Preprint, arXiv:2210.11338, 2022.
- Chong Shangguan and Itzhak Tamo, Degenerate Turán densities of sparse hypergraphs, J. Combin. Theory Ser. A 173 (2020), 105228, 25. MR 4064854, DOI 10.1016/j.jcta.2020.105228
Bibliographic Information
- Michelle Delcourt
- Affiliation: Department of Mathematics, Toronto Metropolitan University (Formerly Named Ryerson University), Toronto, Ontario M5B 2K3, Canada
- MR Author ID: 923919
- Email: mdelcourt@torontomu.ca
- Luke Postle
- Affiliation: Combinatorics and Optimization Department, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada
- MR Author ID: 898019
- ORCID: 0000-0002-5023-269X
- Email: lpostle@uwaterloo.ca
- Received by editor(s): November 7, 2022
- Received by editor(s) in revised form: June 9, 2023, and September 14, 2023
- Published electronically: March 1, 2024
- Additional Notes: The first author’s research was supported by NSERC under Discovery Grant No. 2019-04269. The second author was partially supported by NSERC under Discovery Grant No. 2019-04304
- Communicated by: Isabella Novik
- © Copyright 2024 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 152 (2024), 1881-1891
- MSC (2020): Primary 05C65, 05B07, 05C35, 05D05
- DOI: https://doi.org/10.1090/proc/16668
- MathSciNet review: 4728459