A Caltech Library Service

Hypergraph Ramsey numbers

Conlon, David and Fox, Jacob and Sudakov, Benny (2010) Hypergraph Ramsey numbers. Journal of the American Mathematical Society, 23 (1). pp. 247-266. ISSN 0894-0347.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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 ≥ 3 and s fixed. In particular, we show that r_(3)(s, n) ≤ 2^(n^(s-2)log n), which improves by a factor of n^(s-2)/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) ≥ 2^(csn log((n/s)+1)) for all 4 ≤ s ≤ 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) ≥ 2^(n^(c log n)). Finally, we make some progress on related hypergraph Ramsey-type problems.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Conlon, David0000-0001-5899-1829
Additional Information:© Copyright 2009 American Mathematical Society. The copyright for this article reverts to public domain 28 years after publication. Received by editor(s): September 8, 2008. Published electronically: August 18, 2009. 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. The results in Section 6.1 were obtained in collaboration with Noga Alon, and we thank him for allowing us to include them here. We also thank N. Alon and D. Mubayi for interesting discussions, and the anonymous referee for very useful comments.
Funding AgencyGrant Number
St. John's College, CambridgeUNSPECIFIED
Princeton UniversityUNSPECIFIED
Binational Science Foundation (USA-Israel)UNSPECIFIED
Issue or Number:1
Classification Code:Primary 05C55, 05C65, 05D10
Record Number:CaltechAUTHORS:20190812-163000262
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:97837
Deposited By: Melissa Ray
Deposited On:16 Aug 2019 14:42
Last Modified:03 Oct 2019 21:35

Repository Staff Only: item control page