An improved upper bound for the grid Ramsey problem

Abstract

For a positive integer $r$, let $G(r)$ be the smallest $N$ such that, whenever the edges of the Cartesian product $K_N\times K_N$ are $r$-coloured, then there is a rectangle in which both pairs of opposite edges receive the same colour. In this paper, we improve the upper bounds on $G(r)$ by proving $G(r)\le (1-\frac{1}{128}{r}^{-2})r^{\left(\genfrac{}{}{0ex}{}{r+1}{2}\right)}$, for $r$ large enough. Unlike the previous improvements, which were based on bounds for the size of set systems with restricted intersection sizes, our proof is a form of a quasirandomness argument.

9 pages