Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published August 2008 | public
Journal Article

A new upper bound for the bipartite Ramsey problem


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 Information

© 2008 Wiley. Issue online 17 June 2008; version of record online 28 May 2008; manuscript revised 21 March 2008; manuscript received 24 May 2007.

Additional details

August 22, 2023
October 18, 2023