Remote Access Journal of the American Mathematical Society
Green Open Access

Journal of the American Mathematical Society

ISSN 1088-6834(online) ISSN 0894-0347(print)

 
 

 

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

$\displaystyle 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

$\displaystyle 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

$\displaystyle r_3(n,n,n) \geq 2^{n^{c \log n}}.$

Finally, we make some progress on related hypergraph Ramsey-type problems.


References [Enhancements On Off] (What's this?)

  • 1. M. Ajtai, J. Komlós, and E. Szemerédi, A note on Ramsey numbers, J. Combinatorial Theory, Ser. A 29 (1980), 354-360. MR 600598 (82a:05064)
  • 2. N. Alon and J. H. Spencer, The probabilistic method, 2nd ed., Wiley, 2000. MR 1885388 (2003f:60003)
  • 3. T. Bohman, The Triangle-Free Process, Advances in Mathematics 221 (2009), 1653-1677.
  • 4. H. Burkill and L. Mirsky, Monotonicity, J. Math. Anal. Appl. 41 (1973), 391-410. MR 0335714 (49:494)
  • 5. F. Chung and R. Graham, Erdős on Graphs. His Legacy of Unsolved Problems, A K Peters, Ltd., Wellesley, MA, 1998. MR 1601954 (99b:05031)
  • 6. D. Conlon, A new upper bound for diagonal Ramsey numbers, Annals of Mathematics, to appear.
  • 7. D. Conlon, J. Fox, and B. Sudakov, Ramsey numbers of sparse hypergraphs, Random Structures and Algorithms 35 (2009), 1-14.
  • 8. P. Erdős, Some remarks on the theory of graphs, Bull. Amer. Math. Soc. 53 (1947), 292-294. MR 0019911 (8:479d)
  • 9. P. Erdős, On extremal problems of graphs and generalized graphs, Israel J. Math. 2 (1964), 183-190. MR 0183654 (32:1134)
  • 10. 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.
  • 11. P. Erdős, On some extremal problems on $ r$-graphs, Discrete Math. 1 (1971/72), 1-6. MR 0297602 (45:6656)
  • 12. P. Erdős, Problems and results on graphs and hypergraphs: similarities and differences, in Mathematics of Ramsey theory, Algorithms Combin., Vol. 5 (J. Nešetril and V. Rödl, eds.) 12-28. Berlin: Springer-Verlag, 1990. MR 1083590
  • 13. P. Erdős and A. Hajnal, On Ramsey like theorems, Problems and results, Combinatorics (Proc. Conf. Combinatorial Math., Math. Inst., Oxford, 1972), pp. 123-140, Inst. Math. Appl., Southend-on-Sea, 1972. MR 0337636 (49:2405)
  • 14. P. Erdős and A. Hajnal, Ramsey-type theorems, Discrete Appl. Math. 25 (1989), 37-52. MR 1031262 (90m:05091)
  • 15. P. Erdős, A. Hajnal, and R. Rado, Partition relations for cardinal numbers, Acta Math. Acad. Sci. Hungar. 16 (1965), 93-196. MR 0202613 (34:2475)
  • 16. P. Erdős and R. Rado, Combinatorial theorems on classifications of subsets of a given set, Proc. London Math. Soc. 3 (1952), 417-439. MR 0065615 (16:455d)
  • 17. P. Erdős and G. Szekeres,
    A combinatorial problem in geometry,
    Compositio Math. 2 (1935), 463-470. MR 1556929
  • 18. 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 (2003k:05083)
  • 19. E. Friedgut, Y. Kohayakawa, V. Rödl, A. Ruciński, and P. Tetali, Ramsey games against a one-armed bandit, Combin. Prob. Comp. 12 (2003), 515-545. MR 2037068 (2004m:91047)
  • 20. R. L. Graham, B. L. Rothschild, and J. H. Spencer, Ramsey theory, 2nd edition, John Wiley & Sons (1980). MR 591457 (82b:05001)
  • 21. J. H. Kim, The Ramsey number $ R(3,t)$ has order of magnitude $ t^2/\log t$, Random Structures and Algorithms 7 (1995), 173-207. MR 1369063 (96m:05140)
  • 22. A. V. Kostochka and V. Rödl, On Ramsey numbers of uniform hypergraphs with given maximum degree, J. Combin. Theory Ser. A 113 (2006), 1555-1564. MR 2259079 (2007f:05119)
  • 23. T. Kövari, V. Sós, and P. Turán, On a problem of K. Zarankiewicz, Colloq. Math. 3 (1954), 50-57. MR 0065617 (16:456a)
  • 24. A. Kurek and A. Ruciński, Two variants of the size Ramsey number, Discuss. Math. Graph Theory 25 (2005), 141-149. MR 2152058 (2006a:05101)
  • 25. L. Lovász, Combinatorial problems and exercises, Corrected reprint of the 1993 second edition. AMS Chelsea Publishing, Providence, RI, 2007. MR 2321240
  • 26. V. Nikiforov, Complete $ r$-partite subgraphs of dense $ r$-graphs, Discrete Math. 309 (2009), 4326-4331.
  • 27. F.P. Ramsey, On a problem of formal logic, Proc. London Math. Soc. Ser. 2 30 (1930), 264-286.
  • 28. J. Spencer, Asymptotic lower bounds for Ramsey functions, Discrete Math. 20 (1977/78), 69-76. MR 0491337 (58:10600)

Similar Articles

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
Email: D.Conlon@dpmms.cam.ac.uk

Jacob Fox
Affiliation: Department of Mathematics, Princeton University, Princeton, New Jersey 08544
Email: jacobfox@math.princeton.edu

Benny Sudakov
Affiliation: Department of Mathematics, UCLA, Los Angeles, California 90095
Email: bsudakov@math.ucla.edu

DOI: https://doi.org/10.1090/S0894-0347-09-00645-6
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.

American Mathematical Society