A note on the Erdős-Hajnal hypergraph Ramsey problem

Mubayi, Dhruv; Suk, Andrew; Zhu, Emily

doi:10.1090/proc/15839

A note on the Erdős-Hajnal hypergraph Ramsey problem
HTML articles powered by AMS MathViewer

by Dhruv Mubayi, Andrew Suk and Emily Zhu PDF

Proc. Amer. Math. Soc. 150 (2022), 3675-3685 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
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