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 November 28, 2013 | Submitted
Journal Article Open

# Two extensions of Ramsey's theorem

## Abstract

Ramsey's theorem, in the version of Erdő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 Erdő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 a_1 < • • • < a_k 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, Erdő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 Duke University Press. Received 6 January 2012. Revision received 26 February 2013. First available in Project Euclid 28 November 2013. Conlon's work partially supported by a Royal Society University Research Fellowship. Fox's work partially supported by a Simons Fellowship, by National Science Foundation grant DMS-1069197, by an Alfred P. Sloan Fellowship, and by an MIT NEC Corporation Award. Sudakov's work partially supported by National Science Foundation grant DMS-1101185 and by a US-Israel Binational Science Foundation grant. We would like to thank Noga Alon for helpful discussions and, in particular, for raising the question of what other weight functions might work in Erdős's conjecture. We would also like to thank the referees for their many helpful remarks.

## Attached Files

Submitted - 1112.1548.pdf

## Files

1112.1548.pdf
Files (258.0 kB)
Name Size
md5:5f46386d8b5d66d8c3c74422f335b2d9
258.0 kB