Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published June 2013 | Submitted
Journal Article Open

An improved bound for the stepping-up lemma


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.

Additional Information

© 2010 Elsevier B.V. Under an Elsevier user license. Received 1 July 2009; received in revised form 18 October 2010; accepted 24 October 2010; available online 27 November 2010. The first author's research was supported by a research fellowship from St John's College. The second author's research was supported by an NSF Graduate Research Fellowship and a Princeton Centennial Fellowship. The third author's research was supported by NSF CAREER award DMS-0812005 and by a USA-Israeli BSF grant.

Attached Files

Submitted - 0711.5004.pdf


Files (137.1 kB)
Name Size Download all
137.1 kB Preview Download

Additional details

August 22, 2023
October 18, 2023