Skip to Main Content

Journal of the American Mathematical Society

Published by the American Mathematical Society, the Journal of the American Mathematical Society (JAMS) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

ISSN 1088-6834 (online) ISSN 0894-0347 (print)

The 2020 MCQ for Journal of the American Mathematical Society is 4.79.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Hypergraph Ramsey numbers
HTML articles powered by AMS MathViewer

by David Conlon, Jacob Fox and Benny Sudakov PDF
J. Amer. Math. Soc. 23 (2010), 247-266 Request permission

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
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
  • Email: D.Conlon@dpmms.cam.ac.uk
  • Jacob Fox
  • Affiliation: Department of Mathematics, Princeton University, Princeton, New Jersey 08544
  • MR Author ID: 775407
  • Email: jacobfox@math.princeton.edu
  • Benny Sudakov
  • Affiliation: Department of Mathematics, UCLA, Los Angeles, California 90095
  • MR Author ID: 602546
  • Email: bsudakov@math.ucla.edu
  • 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
  • © Copyright 2009 American Mathematical Society
    The copyright for this article reverts to public domain 28 years after publication.
  • 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
  • MathSciNet review: 2552253