TWO EXTENSIONS OF RAMSEY'S THEOREM - Conlon, D; Fox, J; Sudakov, B (2013)
Ramsey's theorem, in the version of Erdodouble acutes 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 Erdodouble acutes 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, Erdodouble acutes, 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.