## Hypergraph Ramsey numbers

HTML articles powered by AMS MathViewer

- by David Conlon, Jacob Fox and Benny Sudakov PDF
- J. Amer. Math. Soc.
**23**(2010), 247-266 Request permission

## Abstract:

The Ramsey number $r_k(s,n)$ is the minimum $N$ such that every red-blue coloring of the $k$-tuples of an $N$-element set contains a red set of size $s$ or a blue set of size $n$, where a set is called red (blue) if all $k$-tuples from this set are red (blue). In this paper we obtain new estimates for several basic hypergraph Ramsey problems. We give a new upper bound for $r_k(s,n)$ for $k \geq 3$ and $s$ fixed. In particular, we show that \[ r_3(s,n) \leq 2^{n^{s-2}\log n},\] which improves by a factor of $n^{s-2}/\textrm {polylog} n$ the exponent of the previous upper bound of Erdős and Rado from 1952. We also obtain a new lower bound for these numbers, showing that there is a constant $c>0$ such that \[ r_3(s,n) \geq 2^{c sn \log (\frac {n}{s}+1)}\] for all $4 \leq s \leq n$. For constant $s$, this gives the first superexponential lower bound for $r_3(s,n)$, answering an open question posed by Erdős and Hajnal in 1972. Next, we consider the $3$-color Ramsey number $r_3(n,n,n)$, which is the minimum $N$ such that every $3$-coloring of the triples of an $N$-element set contains a monochromatic set of size $n$. Improving another old result of Erdős and Hajnal, we show that \[ r_3(n,n,n) \geq 2^{n^{c \log n}}.\] Finally, we make some progress on related hypergraph Ramsey-type problems.## 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 - Noga Alon and Joel H. Spencer,
*The probabilistic method*, 2nd ed., Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience [John Wiley & Sons], New York, 2000. With an appendix on the life and work of Paul Erdős. MR**1885388**, DOI 10.1002/0471722154 - T. Bohman, The Triangle-Free Process,
*Advances in Mathematics***221**(2009), 1653–1677. - H. Burkill and L. Mirsky,
*Monotonicity*, J. Math. Anal. Appl.**41**(1973), 391–410. MR**335714**, DOI 10.1016/0022-247X(73)90214-X - Fan Chung and Ron Graham,
*Erdős on graphs*, A K Peters, Ltd., Wellesley, MA, 1998. His legacy of unsolved problems. MR**1601954**, DOI 10.1201/9781439863879 - D. Conlon, A new upper bound for diagonal Ramsey numbers,
*Annals of Mathematics*, to appear. - D. Conlon, J. Fox, and B. Sudakov, Ramsey numbers of sparse hypergraphs,
*Random Structures and Algorithms***35**(2009), 1–14. - 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,
*On extremal problems of graphs and generalized graphs*, Israel J. Math.**2**(1964), 183–190. MR**183654**, DOI 10.1007/BF02759942 - P. Erdős, Topics in combinatorial analysis, Proceedings of the Second Louisiana Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, 1971), pp. 2–20, Louisiana State University, Baton Rouge, LA, 1971.
- P. Erdős,
*On some extremal problems on $r$-graphs*, Discrete Math.**1**(1971/72), no. 1, 1–6. MR**297602**, DOI 10.1016/0012-365X(71)90002-1 - Paul Erdős,
*Problems and results on graphs and hypergraphs: similarities and differences*, Mathematics of Ramsey theory, Algorithms Combin., vol. 5, Springer, Berlin, 1990, pp. 12–28. MR**1083590**, DOI 10.1007/978-3-642-72905-8_{2} - 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 and A. Hajnal,
*Ramsey-type theorems*, Discrete Appl. Math.**25**(1989), no. 1-2, 37–52. Combinatorics and complexity (Chicago, IL, 1987). MR**1031262**, DOI 10.1016/0166-218X(89)90045-0 - 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** - R. J. Faudree and R. H. Schelp,
*A survey of results on the size Ramsey number*, Paul Erdős and his mathematics, II (Budapest, 1999) Bolyai Soc. Math. Stud., vol. 11, János Bolyai Math. Soc., Budapest, 2002, pp. 291–309. MR**1954730** - Ehud Friedgut, Yoshiharu Kohayakawa, Vojtěch Rödl, Andrzej Ruciński, and Prasad Tetali,
*Ramsey games against a one-armed bandit*, Combin. Probab. Comput.**12**(2003), no. 5-6, 515–545. Special issue on Ramsey theory. MR**2037068**, DOI 10.1017/S0963548303005881 - Ronald L. Graham, Bruce L. Rothschild, and Joel H. Spencer,
*Ramsey theory*, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, Inc., New York, 1980. MR**591457** - Jeong Han Kim,
*The Ramsey number $R(3,t)$ has order of magnitude $t^2/\log t$*, Random Structures Algorithms**7**(1995), no. 3, 173–207. MR**1369063**, DOI 10.1002/rsa.3240070302 - A. V. Kostochka and V. Rödl,
*On Ramsey numbers of uniform hypergraphs with given maximum degree*, J. Combin. Theory Ser. A**113**(2006), no. 7, 1555–1564. MR**2259079**, DOI 10.1016/j.jcta.2005.12.007 - T. Kövari, V. T. Sós, and P. Turán,
*On a problem of K. Zarankiewicz*, Colloq. Math.**3**(1954), 50–57. MR**65617**, DOI 10.4064/cm-3-1-50-57 - Andrzej Kurek and Andrzej Ruciński,
*Two variants of the size Ramsey number*, Discuss. Math. Graph Theory**25**(2005), no. 1-2, 141–149. MR**2152058**, DOI 10.7151/dmgt.1268 - László Lovász,
*Combinatorial problems and exercises*, 2nd ed., AMS Chelsea Publishing, Providence, RI, 2007. MR**2321240**, DOI 10.1090/chel/361 - V. Nikiforov, Complete $r$-partite subgraphs of dense $r$-graphs,
*Discrete Math.***309**(2009), 4326–4331. - F.P. Ramsey, On a problem of formal logic,
*Proc. London Math. Soc. Ser. 2***30**(1930), 264–286. - 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

## Additional Information

**David Conlon**- Affiliation: St John’s College, Cambridge CB2 1TP, United Kingdom
- MR Author ID: 793461
- Email: D.Conlon@dpmms.cam.ac.uk
**Jacob Fox**- Affiliation: Department of Mathematics, Princeton University, Princeton, New Jersey 08544
- MR Author ID: 775407
- Email: jacobfox@math.princeton.edu
**Benny Sudakov**- Affiliation: Department of Mathematics, UCLA, Los Angeles, California 90095
- MR Author ID: 602546
- Email: bsudakov@math.ucla.edu
- Received by editor(s): September 8, 2008
- Published electronically: August 18, 2009
- Additional Notes: The research of the first author was supported by a Junior Research Fellowship at St John’s College, Cambridge

The research of the second author was supported by an NSF Graduate Research Fellowship and a Princeton Centennial Fellowship

The research of the third author was supported in part by NSF CAREER award DMS-0812005 and by a USA-Israeli BSF grant - © Copyright 2009
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication. - Journal: J. Amer. Math. Soc.
**23**(2010), 247-266 - MSC (2000): Primary 05C55, 05C65, 05D10
- DOI: https://doi.org/10.1090/S0894-0347-09-00645-6
- MathSciNet review: 2552253