Ramsey numbers of cubes versus cliques
The cube graph Q[subscript n] is the skeleton of the n-dimensional cube. It is an n-regular graph on 2[superscript n] vertices. The Ramsey number r(Q[subscript n] ;K[subscript s]) is the minimum N such that every graph of order N contains the cube graph Q[subscript n] or an independent set of order...
| Hauptverfasser: | , , , |
|---|---|
| Weitere Verfasser: | |
| Format: | Artikel |
| Sprache: | en_US |
| Veröffentlicht: |
Springer-Verlag/Bolyai Society
2015
|
| Online Zugang: | http://hdl.handle.net/1721.1/92844 https://orcid.org/0000-0002-5798-3509 |
| _version_ | 1826199421117792256 |
|---|---|
| author | Conlon, David Fox, Jacob Lee, Choongbum Sudakov, Benny |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Conlon, David Fox, Jacob Lee, Choongbum Sudakov, Benny |
| author_sort | Conlon, David |
| collection | MIT |
| description | The cube graph Q[subscript n] is the skeleton of the n-dimensional cube. It is an n-regular graph on 2[superscript n] vertices. The Ramsey number r(Q[subscript n] ;K[subscript s]) is the minimum N such that every graph of order N contains the cube graph Q[subscript n] or an independent set of order s. In 1983, Burr and Erdős asked whether the simple lower bound r(Q[subscript n] ;K[subscript s] )≥(s−1)(2[superscript 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. |
| first_indexed | 2024-09-23T11:19:56Z |
| format | Article |
| id | mit-1721.1/92844 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:19:56Z |
| publishDate | 2015 |
| publisher | Springer-Verlag/Bolyai Society |
| record_format | dspace |
| spelling | mit-1721.1/928442022-10-01T02:51:59Z Ramsey numbers of cubes versus cliques Conlon, David Fox, Jacob Lee, Choongbum Sudakov, Benny Massachusetts Institute of Technology. Department of Mathematics Fox, Jacob Lee, Choongbum The cube graph Q[subscript n] is the skeleton of the n-dimensional cube. It is an n-regular graph on 2[superscript n] vertices. The Ramsey number r(Q[subscript n] ;K[subscript s]) is the minimum N such that every graph of order N contains the cube graph Q[subscript n] or an independent set of order s. In 1983, Burr and Erdős asked whether the simple lower bound r(Q[subscript n] ;K[subscript s] )≥(s−1)(2[superscript 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. Swiss National Science Foundation (SNSF grant 200021-149111) United States-Israel Binational Science Foundation Samsung (Firm) (Scholarship) Royal Society (Great Britain) (University Research Fellowship) David & Lucile Packard Foundation (Fellowship) Simons Foundation (Fellowship) NEC Corporation (MIT NEC Corp. award) National Science Foundation (U.S.) (NSF grant DMS-1069197) 2015-01-13T22:22:18Z 2015-01-13T22:22:18Z 2014-11 2012-08 Article http://purl.org/eprint/type/JournalArticle 0209-9683 1439-6912 http://hdl.handle.net/1721.1/92844 Conlon, David, Jacob Fox, Choongbum Lee, and Benny Sudakov. “Ramsey Numbers of Cubes Versus Cliques.” Combinatorica (November 5, 2014). https://orcid.org/0000-0002-5798-3509 en_US http://dx.doi.org/10.1007/s00493-014-3010-x Combinatorica Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Springer-Verlag/Bolyai Society arXiv |
| spellingShingle | Conlon, David Fox, Jacob Lee, Choongbum Sudakov, Benny Ramsey numbers of cubes versus cliques |
| title | Ramsey numbers of cubes versus cliques |
| title_full | Ramsey numbers of cubes versus cliques |
| title_fullStr | Ramsey numbers of cubes versus cliques |
| title_full_unstemmed | Ramsey numbers of cubes versus cliques |
| title_short | Ramsey numbers of cubes versus cliques |
| title_sort | ramsey numbers of cubes versus cliques |
| url | http://hdl.handle.net/1721.1/92844 https://orcid.org/0000-0002-5798-3509 |
| work_keys_str_mv | AT conlondavid ramseynumbersofcubesversuscliques AT foxjacob ramseynumbersofcubesversuscliques AT leechoongbum ramseynumbersofcubesversuscliques AT sudakovbenny ramseynumbersofcubesversuscliques |