An improved bound for the stepping-up lemma

Details An improved bound for the stepping-up lemma An improved bound for the stepping-up lemma

2009-07-02

arxiv.org/abs/0907.0283v1

Mathematics

Combinatorics

8 pages

Scientific paper

The partition relation N \to (n)_{\ell}^k means that whenever the k-tuples of an N-element set are \ell-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 \to (n)_{\ell}^k is written as N \not \to (n)_{\ell}^k. An ingenious construction of Erd\H{o}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 \ell \geq 2, k \geq 3, and N \not \to (n)_{\ell}^k, then 2^N \not \to (2n+k-4)_{\ell}^{k+1}. In this note we give an improved construction for k \geq 4. We introduce a general class of colorings which extends the framework of Erd\H{o}s and Hajnal and can be used to establish negative partition relations. We show that if \ell \geq 2, k \geq 4 and N \not \to (n)_{\ell}^k, then 2^N \not \to (n+3)_{\ell}^{k+1}. If also k is odd or \ell \geq 3, then we get the better bound 2^N \not \to (n+2)_{\ell}^{k+1}. This improved bound gives a coloring of the k-tuples whose largest monochromatic set is a factor \Omega(2^{k}) smaller than 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 \ell \geq 4 we determine up to an absolute constant factor (which is independent of k) the size of the largest guaranteed monochromatic set in an \ell-coloring of the k-tuples of an N-set.

Affiliated with

Also associated with

No associations

Rating

An improved bound for the stepping-up lemma does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An improved bound for the stepping-up lemma, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An improved bound for the stepping-up lemma will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-730686