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 KN × KN are r-colored, then there is a rectangle in which both pairs of opposite edges receive the same color. In this paper, we improve the upper bounds on G (r) by proving (Formula presented.), 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 quasirandomness argument.