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 is the minimum such that every red-blue coloring of the -tuples of an -element set contains a red set of size or a blue set of size , where a set is called red (blue) if all -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 for and fixed. In particular, we show that

**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 -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 has order of magnitude ,*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 -partite subgraphs of dense -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)**

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.