Hypergraph Ramsey numbers

Source abstract

The Ramsey number r k ( s , n ) r_k(s,n) is the minimum N N such that every red-blue coloring of the k k -tuples of an N N -element set contains a red set of size s s or a blue set of size n n , where a set is called red (blue) if all k 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 ) r_k(s,n) for k ≥ 3 k \geq 3 and s s fixed. In particular, we show that $$r 3 ( s , n ) ≤ 2 n s − 2 log ⁡ n , r_3(s,n) \leq 2^{n^{s-2}\log n},$$ which improves by a factor of n s − 2 / polylog n 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 c>0 such that $$r 3 ( s , n ) ≥ 2 c s n log ⁡ ( n s + 1 ) r_3(s,n) \geq 2^{c \, sn \, \log (\frac {n}{s}+1)}$$ for all 4 ≤ s ≤ n 4 \leq s \leq n . For constant s s , this gives the first superexponential lower bound for r 3 ( s , n ) r_3(s,n) , answering an open question posed by Erdős and Hajnal in 1972. Next, we consider the 3 3 -color Ramsey number r 3 ( n , n , n ) r_3(n,n,n) , which is the minimum N N such that every 3 3 -coloring of the triples of an N N -element set contains a monochromatic set of size n n . Improving another old result of Erdős and Hajnal, we show that $$r 3 ( n , n , n ) ≥ 2 n c log ⁡ n . r_3(n,n,n) \geq 2^{n^{c \log n}}.$$ Finally, we make some progress on related hypergraph Ramsey-type problems.