Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Journal of the American Mathematical Society
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

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?)


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: http://dx.doi.org/10.1090/S0894-0347-09-00645-6
PII: S 0894-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.