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 $0.5log_2 n$. In this talk, we
consider two well-studied extensions of Ramsey’s theorem.
We show that there is a constant $c0$ such that every $2$-coloring of the edges of the complete graph on $2,…,n$ contains a monochromatic clique such
that the sum of $1/log i$ over all vertices $i$ of this monochromatic clique is at least $clogloglog n$, which is tight apart from the constant factor $c$.
This extends an earlier work of Rodl 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 every $2$-coloring of the edges of the complete graph
on $1,…,n$ contains a monochromatic clique $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 growth rate should be exponential in $k$.
We make progress on this conjecture, obtaining an upper bound on $n$ which is exponential in a power of $k$. This improves on a result of Shelah, who showed that $ $ at most double-exponential in $k$.
The proofs of the above results use the powerful probabilistic technique known as dependent random choice, with some additional combinatorial ideas.
Joint work with David Conlon and Benny Sudakov.