Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published January 2010 | Submitted
Journal Article Open

Hypergraph Ramsey numbers


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.

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.

Attached Files

Submitted - 0808.3760.pdf


Files (259.1 kB)
Name Size Download all
259.1 kB Preview Download

Additional details

August 19, 2023
October 12, 2023