| الملخص: | Ramsey's theorem, in the version of Erdo{double acute}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 article, we consider two well-studied extensions of Ramsey's theorem. Improving a result of Rödl, 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εS is at least c log log log n. This is tight up to the constant factor c and answers a question of Erdo{double acute}s from 1981. Motivated by a problem in model theory, Väänänen asked whether for every k there is an n such that the following holds: for every permutation π of 1,.,k-1, every 2-coloring of the edges of the complete graph on {1,2,.,n} contains a monochromatic clique a1 < < ak with aπ(1)+1-aπ(1)>aπ(2)+1-aπ(2)>> aπ(k-1)+1-aπ(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, Erdo{double acute}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. © 2013.
|
|---|