On the Grid Ramsey Problem and Related Questions
The Hales-Jewett theorem is one of the pillars of Ramsey theory, from which many other results follow. A celebrated theorem of Shelah says that Hales-Jewett numbers are primitive recursive. A key tool used in his proof, now known as the cube lemma, has become famous in its own right. In its simplest form, this lemma says that if we color the edges of the Cartesian product K_n x K_n in r colors, then, for n sufficiently large, there is a rectangle with both pairs of opposite edges receiving the same color. Shelah's proof shows that [equation; see abstract in PDF for details] suffices. More than 20 years ago, Graham, Rothschild, and Spencer asked whether this bound can be improved to a polynomial in r. We show that this is not possible by providing a superpolynomial lower bound in r. We also discuss a number of related problems.
Additional Information© The Author(s) 2014. Published by Oxford University Press. Published 24 October 2014; received 26 May 2014; revision received 25 September 2014; accepted 26 September 2014. David Conlon was supported by a Royal Society University Research Fellowship. Jacob Fox was supported by a Packard Fellowship, a Simons Fellowship, NSF CAREER award DMS-1352121, an Alfred P. Sloan Fellowship and an MIT NEC Corporation Award. Choongbum Lee was supported by NSF Grant DMS-1362326. Benny Sudakov was supported by SNSF grant 200021-149111 and a USA-Israel BSF grant. We would like to thank the anonymous referee for several helpful comments.
Published - rnu190.pdf
Submitted - 1405.6587.pdf