Two extensions of Ramsey's theorem

Details Two extensions of Ramsey's theorem Two extensions of Ramsey's theorem

2011-12-07

arxiv.org/abs/1112.1548v1

Mathematics

Combinatorics

20 pages

Scientific paper

Ramsey's theorem, in the version of Erd\H{o}s and Szekeres, states that every 2-coloring of the edges of the complete graph on {1, 2,...,n} contains a monochromatic clique of order 1/2\log n. In this paper, we consider two well-studied extensions of Ramsey's theorem. Improving a result of R\"odl, we show that there is a constant $c>0$ such that every 2-coloring of the edges of the complete graph on \{2, 3,...,n\} contains a monochromatic clique S for which the sum of 1/\log i over all vertices i \in S is at least c\log\log\log n. This is tight up to the constant factor c and answers a question of Erd\H{o}s from 1981. Motivated by a problem in model theory, V\"a\"an\"anen asked whether for every k there is an n such that the following holds. For every permutation \pi of 1,...,k-1, every 2-coloring of the edges of the complete graph on {1, 2, ..., n} contains a monochromatic clique a_1<...a_{\pi(2)+1}-a_{\pi(2)}>...>a_{\pi(k-1)+1}-a_{\pi(k-1)}. That is, not only do we want a monochromatic clique, but the differences between consecutive vertices must satisfy a prescribed order. Alon and, independently, Erd\H{o}s, Hajnal and Pach answered this question affirmatively. Alon further conjectured that the true growth rate should be exponential in k. We make progress towards this conjecture, obtaining an upper bound on n which is exponential in a power of k. This improves a result of Shelah, who showed that n is at most double-exponential in k.

Affiliated with

Also associated with

No associations

Rating

Two extensions of Ramsey's theorem 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 Two extensions of Ramsey's theorem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Two extensions of Ramsey's theorem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-595321