Ramsey numbers of cubes versus cliques
The cube graph Q_n is the skeleton of the n-dimensional cube. It is an n-regular graph on 2^n vertices. The Ramsey number r(Q_n, K_s) is the minimum N such that every graph of order N contains the cube graph Q_n or an independent set of order s. In 1983, Burr and Erdős asked whether the simple lower bound r(Q_n, K_s) ≥ (s−1)(2^(n) − 1) + 1 is tight for s fixed and n sufficiently large. We make progress on this problem, obtaining the first upper bound which is within a constant factor of the lower bound.
Additional Information© 2016 János Bolyai Mathematical Society and Springer-Verlag Berlin Heidelberg. Received 08 August 2012; first online 05 November 2014. Conlon research supported by a Royal Society University Research Fellowship. Fox research supported by a Packard Fellowship, a Simons Fellowship, an MIT NEC Corp. award and NSF grant DMS-1069197. Lee research supported in part by a Samsung Scholarship. Sudakov research supported in part by SNSF grant 200021-149111 and by a USA-Israel BSF grant. We would like to thank the two anonymous referees for their valuable comments.
Submitted - 1208.1732.pdf