An improved bound for the stepping-up lemma

Abstract

The partition relation N → (n)^(k)_(ℓ) means that whenever the k-tuples of an N-element set are ℓ-colored, there is a monochromatic set of size n, where a set is called monochromatic if all its k-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, k ≥ 3, and N / → (n)^(k)_(ℓ), then 2^N / → (2n + k - 4)^(k+1)_(ℓ). In this paper we give an improved construction for k ≥ 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, k ≥ 4 and N / → (n)^(k)_(ℓ), then 2^N / → (n + 3)^(k+1)_(ℓ). If also k is odd or ℓ ≥ 3, then we get the better bound 2^N / → (n + 2)^(k+1)_(ℓ). This improved bound gives a coloring of the k-tuples whose largest monochromatic set is a factor Ω(2^k) 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 we determine up to an absolute constant factor (which is independent of k) the size of the largest guaranteed monochromatic set in an ℓ-coloring of the k-tuples of an N-set.

Files

Additional details