An improved upper bound for the grid Ramsey problem

For a positive integer r , let G  ( r ) be the smallest N such that, whenever the edges of the Cartesian product K N  ×  K N 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 G ( r ) ≤ ( 1 − 1 128 r − 2( 1 − o ( 1 ) ) ) r ( r + 1 2 ), 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.