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
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.

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


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
MR Author ID: 793461

Jacob Fox
Affiliation: Department of Mathematics, Princeton University, Princeton, New Jersey 08544
MR Author ID: 775407

Benny Sudakov
Affiliation: Department of Mathematics, UCLA, Los Angeles, California 90095
MR Author ID: 602546

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.