Hypergraph Ramsey numbers

Authors:
David Conlon, Jacob Fox and Benny Sudakov

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

Published electronically:
August 18, 2009

MathSciNet review:
2552253

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.

- 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 https://doi.org/10.1016/0097-3165%2880%2990030-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** - 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 https://doi.org/10.1016/0022-247X%2873%2990214-X - Fan Chung and Ron Graham,
*Erdős on graphs*, A K Peters, Ltd., Wellesley, MA, 1998. His legacy of unsolved problems. MR**1601954** - 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 https://doi.org/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 https://doi.org/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 https://doi.org/10.1016/0012-365X%2871%2990002-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 https://doi.org/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 https://doi.org/10.1016/0166-218X%2889%2990045-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 https://doi.org/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 https://doi.org/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 https://doi.org/10.1017/S0963548303005881 - Ronald L. Graham, Bruce L. Rothschild, and Joel H. Spencer,
*Ramsey theory*, John Wiley & Sons, Inc., New York, 1980. Wiley-Interscience Series in Discrete Mathematics; A Wiley-Interscience Publication. 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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/10.7151/dmgt.1268 - László Lovász,
*Combinatorial problems and exercises*, 2nd ed., AMS Chelsea Publishing, Providence, RI, 2007. MR**2321240** - 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 https://doi.org/10.1016/0012-365X%2877%2990044-9

Retrieve articles in *Journal of the American Mathematical Society*
with MSC (2000):
05C55,
05C65,
05D10

Retrieve articles in all journals with MSC (2000): 05C55, 05C65, 05D10

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

Article copyright:
© Copyright 2009
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication.