A note on the grid Ramsey problem

Abstract

The grid Ramsey number $G(r)$ is the smallest number $n$ such that every edge-colouring of the grid graph $\hat{I}{“}_{n,n}:=K_n\times K_n$ with $r$ colours induces a rectangle whose parallel edges receive the same colour. We show $G(r)\le r^{\left(\genfrac{}{}{0ex}{}{r+1}{2}\right)}-\left(1/4-o(1)\right)r^{\left(\genfrac{}{}{0ex}{}{r}{2}\right)+1}$, slightly improving the currently best known upper bound due to Gyárfás.

7 pages