A note on the Erdős-Hajnal hypergraph Ramsey problem
HTML articles powered by AMS MathViewer
- by Dhruv Mubayi, Andrew Suk and Emily Zhu
- Proc. Amer. Math. Soc. 150 (2022), 3675-3685
- DOI: https://doi.org/10.1090/proc/15839
- Published electronically: May 20, 2022
- PDF | Request permission
Abstract:
We show that there is an absolute constant $c>0$ such that the following holds. For every $n > 1$, there is a 5-uniform hypergraph on at least $2^{2^{cn^{1/4}}}$ vertices with independence number at most $n$, where every set of 6 vertices induces at most 3 edges. The double exponential growth rate for the number of vertices is sharp. By applying a stepping-up lemma established by the first two authors, analogous sharp results are proved for $k$-uniform hypergraphs. This answers the penultimate open case of a conjecture in Ramsey theory posed by Erdős and Hajnal in 1972.References
- Miklós Ajtai, János Komlós, and Endre Szemerédi, A note on Ramsey numbers, J. Combin. Theory Ser. A 29 (1980), no. 3, 354–360. MR 600598, DOI 10.1016/0097-3165(80)90030-8
- Tom Bohman, The triangle-free process, Adv. Math. 221 (2009), no. 5, 1653–1677. MR 2522430, DOI 10.1016/j.aim.2009.02.018
- Tom Bohman and Peter Keevash, The early evolution of the $H$-free process, Invent. Math. 181 (2010), no. 2, 291–336. MR 2657427, DOI 10.1007/s00222-010-0247-x
- David Conlon, A new upper bound for diagonal Ramsey numbers, Ann. of Math. (2) 170 (2009), no. 2, 941–960. MR 2552114, DOI 10.4007/annals.2009.170.941
- F. R. K. Chung, Open problems of Paul Erdős in graph theory, J. Graph Theory 25 (1997), no. 1, 3–36. MR 1441976, DOI 10.1002/(SICI)1097-0118(199705)25:1<3::AID-JGT1>3.0.CO;2-R
- David Conlon, Jacob Fox, and Benny Sudakov, Hypergraph Ramsey numbers, J. Amer. Math. Soc. 23 (2010), no. 1, 247–266. MR 2552253, DOI 10.1090/S0894-0347-09-00645-6
- P. Erdös, Some remarks on the theory of graphs, Bull. Amer. Math. Soc. 53 (1947), 292–294. MR 19911, DOI 10.1090/S0002-9904-1947-08785-1
- P. Erdős and H. Hanani, On a limit theorem in combinatorial analysis, Publ. Math. Debrecen 10 (1963), 10–13. MR 166116, DOI 10.5486/pmd.1963.10.1-4.02
- P. Erdős and A. Hajnal, On Ramsey like theorems. Problems and results, Combinatorics (Proc. Conf. Combinatorial Math., Math. Inst., Oxford, 1972) Inst. Math. Appl., Southend-on-Sea, 1972, pp. 123–140. MR 0337636
- P. Erdős, A. Hajnal, and R. Rado, Partition relations for cardinal numbers, Acta Math. Acad. Sci. Hungar. 16 (1965), 93–196. MR 202613, DOI 10.1007/BF01886396
- P. Erdős and R. Rado, Combinatorial theorems on classifications of subsets of a given set, Proc. London Math. Soc. (3) 2 (1952), 417–439. MR 65615, DOI 10.1112/plms/s3-2.1.417
- P. Erdös and G. Szekeres, A combinatorial problem in geometry, Compositio Math. 2 (1935), 463–470. MR 1556929
- Dhruv Mubayi and Andrew Suk, New lower bounds for hypergraph Ramsey numbers, Bull. Lond. Math. Soc. 50 (2018), no. 2, 189–201. MR 3830113, DOI 10.1112/blms.12133
- Dhruv Mubayi and Andrew Suk, The Erdős-Hajnal hypergraph Ramsey problem, J. Eur. Math. Soc. (JEMS) 22 (2020), no. 4, 1247–1259. MR 4071326, DOI 10.4171/JEMS/944
- Joel Spencer, Asymptotic lower bounds for Ramsey functions, Discrete Math. 20 (1977/78), no. 1, 69–76. MR 491337, DOI 10.1016/0012-365X(77)90044-9
Bibliographic Information
- Dhruv Mubayi
- Affiliation: Department of Mathematics, Statistics, and Computer Science, University of Illinois, Chicago, Illinois 60607
- MR Author ID: 637169
- Email: mubayi@uic.edu
- Andrew Suk
- Affiliation: Department of Mathematics, University of California at San Diego, La Jolla, California, 92093
- MR Author ID: 852359
- Email: asuk@ucsd.edu
- Emily Zhu
- Affiliation: Department of Mathematics, University of California at San Diego, La Jolla, California, 92093
- MR Author ID: 1352784
- Email: e9zhu@ucsd.edu
- Received by editor(s): February 28, 2020
- Received by editor(s) in revised form: September 9, 2021
- Published electronically: May 20, 2022
- Additional Notes: The first author was partially supported by NSF grants DMS-1300138, DMS-1763317, and DMS-1952767.
The second author was supported by NSF CAREER award DMS-1800746, by NSF grant DMS-1952786, and by an Alfred Sloan Fellowship.
The third author was partially supported by the National Science Foundation Graduate Research Fellowship Program under Grant No. DGE-2038238. - Communicated by: Patricia L. Hersh
- © Copyright 2022 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 150 (2022), 3675-3685
- MSC (2020): Primary 05D10, 05C65
- DOI: https://doi.org/10.1090/proc/15839
- MathSciNet review: 4446221