A new upper bound for the bipartite Ramsey problem

Abstract

We consider the following question: how large does n have to be to guarantee that in any two‐coloring of the edges of the complete graph K_(n,n) there is a monochromatic K_(k,k)? In the late 1970s, Irving showed that it was sufficient, for k large, that n ≥ 2^(k − 1) (k − 1) − 1. Here we improve upon this bound, showing that it is sufficient to take n ≥ (1 + o(1))2^(k+1) log k, where the log is taken to the base 2.

Additional details