An improved bound for the stepping-up lemma

The partition relation N→(n)ℓk means that whenever the kk-tuples of an NN-element set are ℓℓ-colored, there is a monochromatic set of size nn, where a set is called monochromatic if all its kk-tuples have the same color. The logical negation of N→(n)ℓk is written as N⁄→(n)ℓk. An ingenious construction of Erdős and Hajnal known as the stepping-up lemma gives a negative partition relation for higher uniformity from one of lower uniformity, effectively gaining an exponential in each application. Namely, if ℓ≥2ℓ≥2, k≥3k≥3, and N⁄→(n)ℓk, then 2N⁄→(2n+k−4)ℓk+1. In this paper we give an improved construction for k≥4k≥4. We introduce a general class of colorings which extends the framework of Erdős and Hajnal and can be used to establish negative partition relations. We show that if ℓ≥2ℓ≥2, k≥4k≥4 and N⁄→(n)ℓk, then 2N⁄→(n+3)ℓk+1. If also kk is odd or ℓ≥3ℓ≥3, then we get the better bound 2N⁄→(n+2)ℓk+1. This improved bound gives a coloring of the kk-tuples whose largest monochromatic set is a factor Ω(2k)Ω(2k) smaller than that given by the original version of the stepping-up lemma. We give several applications of our result to lower bounds on hypergraph Ramsey numbers. In particular, for fixed ℓ≥4ℓ≥4 we determine up to an absolute constant factor (which is independent of kk) the size of the largest guaranteed monochromatic set in an ℓℓ-coloring of the kk-tuples of an NN-set.