Hypergraph Ramsey numbers

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

Files

Additional details