# Combinatorics Seminar

When: Sunday, June 8, 10am

Where: Schreiber 309

Speaker: Benny Sudakov, ETH

Title: Grid Ramsey problem and related questions

## Abstract:

The Hales-Jewett theorem is one of the pillars of Ramsey theory, from which
many other results follow. A celebrated result of Shelah says that
Hales-Jewett numbers are primitive recursive. A key tool used in his proof,
known as the cube lemma, has become famous in its own right. In its simplest
form, it says that if we color the edges of the Cartesian product $K_n
\times K_n$ in $r$ colors then, for $n$ sufficiently large, there is a
rectangle with both pairs of opposite edges receiving the same color.

Hoping to improve Shelah's result, Graham, Rothschild and Spencer asked more
than 20 years ago whether the cube lemma holds with $n$
which is polynomial in $r$. We show that this is not possible by providing
a superpolynomial lower bound in $r$. We also discuss a number of related
questions, among them a solution of a problem of Erdos and Gyarfas on
generalized Ramsey numbers.

Joint work with Conlon, Fox and Lee.

redesigned by barak soreq