The ACO Seminar (2011-2012)

A vertex subset is homogeneous if it is either a clique or independent set. Ramsey's theorem, in the version of Erdos and Szekeres, states that every 2-coloring of the edges of the complete graph on 1,...,n contains a monochromatic clique of order (1/2)log n. In this talk, we consider two well-studied extensions of Ramsey's theorem.

Improving a result of Rodl, we show that there is a constant c > 0 such that every 2-coloring of the edges of the complete graph on 2,...,n contains a monochromatic clique S such that the sum of 1/log i over all vertices i in S is at least clogloglog n. This is tight up to the constant factor c and answers a question of Erdos from 1981.

Motivated by a problem in model theory, Vaananen asked whether for every k there is an n such that the following holds. Every 2-coloring of the edges of the complete graph on 1,...,n contains a monochromatic clique with vertices a_1 < ... < a_k such that the differences a_{i+1}-a_i satisfy a prescribed order relation. Alon and independently Erdos, Hajnal, and Pach answered this question affirmatively. Alon further conjectured that the true growth rate should be exponential in n. We make progress on this conjecture, obtaining an upper bound 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.

The proofs of the above results use a powerful probabilistic technique known as dependent random choice. Joint work with David Conlon and Benny Sudakov.