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 February 2016 | Submitted
Journal Article Open

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.

Attached Files

Submitted - 1208.1732.pdf


Files (296.0 kB)
Name Size Download all
296.0 kB Preview Download

Additional details

August 20, 2023
October 18, 2023