Published February 2016
| Submitted
Journal Article
Open
Ramsey numbers of cubes versus cliques
Abstract
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
1208.1732.pdf
Files
(296.0 kB)
Name | Size | Download all |
---|---|---|
md5:58bffdbe17f97fb8044bc4614b65e8d4
|
296.0 kB | Preview Download |
Additional details
- Eprint ID
- 97825
- Resolver ID
- CaltechAUTHORS:20190812-162959158
- Royal Society
- David and Lucile Packard Foundation
- Simons Foundation
- MIT NEC Corporation
- DMS-1069197
- NSF
- Samsung
- 200021-149111
- Swiss National Science Foundation (SNSF)
- Binational Science Foundation (USA-Israel)
- Created
-
2019-08-14Created from EPrint's datestamp field
- Updated
-
2021-11-16Created from EPrint's last_modified field