On two problems in graph Ramsey theory
We study two classical problems in graph Ramsey theory, that of determining the Ramsey number of bounded-degree graphs and that of estimating the induced Ramsey number for a graph with a given number of vertices. The Ramsey number r(H) of a graph H is the least positive integer N such that every...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer-Verlag
2012
|
| Online Access: | http://hdl.handle.net/1721.1/71250 |
| _version_ | 1826212321887780864 |
|---|---|
| author | Conlon, David Fox, Jacob Sudakov, Benny |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Conlon, David Fox, Jacob Sudakov, Benny |
| author_sort | Conlon, David |
| collection | MIT |
| description | We study two classical problems in graph Ramsey theory, that of determining the Ramsey
number of bounded-degree graphs and that of estimating the induced Ramsey number for a graph
with a given number of vertices.
The Ramsey number r(H) of a graph H is the least positive integer N such that every twocoloring
of the edges of the complete graph KN contains a monochromatic copy of H. A famous
result of Chv atal, Rodl, Szemer edi and Trotter states that there exists a constant c( Delta) such that
r(H) c(Delta )n for every graph H with n vertices and maximum degree . The important open
question is to determine the constant c(Delta ). The best results, both due to Graham, Rodl and
Ruci nski, state that there are constants c and c0 such that 2c0 Delta[less than or equal to] c( Delta) 2c Deltalog2Delta . We improve this upper bound, showing that there is a constant c for which c(Delta )[less than or equal to] 2cDelta log Delta.
The induced Ramsey number rind(H) of a graph H is the least positive integer N for which
there exists a graph G on N vertices such that every two-coloring of the edges of G contains an
induced monochromatic copy of H. Erdos conjectured the existence of a constant c such that,
for any graph H on n vertices, rind(H) 2cn. We move a step closer to proving this conjecture,
showing that rind(H)[less than or equal to] 2cn log n. This improves upon an earlier result of Kohayakawa, Promel and Rodl by a factor of log n in the exponent. |
| first_indexed | 2024-09-23T15:19:52Z |
| format | Article |
| id | mit-1721.1/71250 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T15:19:52Z |
| publishDate | 2012 |
| publisher | Springer-Verlag |
| record_format | dspace |
| spelling | mit-1721.1/712502022-10-02T02:12:19Z On two problems in graph Ramsey theory Conlon, David Fox, Jacob Sudakov, Benny Massachusetts Institute of Technology. Department of Mathematics Fox, Jacob Fox, Jacob We study two classical problems in graph Ramsey theory, that of determining the Ramsey number of bounded-degree graphs and that of estimating the induced Ramsey number for a graph with a given number of vertices. The Ramsey number r(H) of a graph H is the least positive integer N such that every twocoloring of the edges of the complete graph KN contains a monochromatic copy of H. A famous result of Chv atal, Rodl, Szemer edi and Trotter states that there exists a constant c( Delta) such that r(H) c(Delta )n for every graph H with n vertices and maximum degree . The important open question is to determine the constant c(Delta ). The best results, both due to Graham, Rodl and Ruci nski, state that there are constants c and c0 such that 2c0 Delta[less than or equal to] c( Delta) 2c Deltalog2Delta . We improve this upper bound, showing that there is a constant c for which c(Delta )[less than or equal to] 2cDelta log Delta. The induced Ramsey number rind(H) of a graph H is the least positive integer N for which there exists a graph G on N vertices such that every two-coloring of the edges of G contains an induced monochromatic copy of H. Erdos conjectured the existence of a constant c such that, for any graph H on n vertices, rind(H) 2cn. We move a step closer to proving this conjecture, showing that rind(H)[less than or equal to] 2cn log n. This improves upon an earlier result of Kohayakawa, Promel and Rodl by a factor of log n in the exponent. 2012-06-28T13:56:24Z 2012-06-28T13:56:24Z 2012-05 Article http://purl.org/eprint/type/JournalArticle 0209-9683 1439-6912 http://hdl.handle.net/1721.1/71250 Conlon, David, Jacob Fox and Benny Sudakov. "On two problems in graph Ramsey theory." Combinatorica 32 (5) (2012), p.513-535. en_US http://dx.doi.org/10.1007/s00493-012-2710-3 Combinatorica Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Springer-Verlag MIT web domain |
| spellingShingle | Conlon, David Fox, Jacob Sudakov, Benny On two problems in graph Ramsey theory |
| title | On two problems in graph Ramsey theory |
| title_full | On two problems in graph Ramsey theory |
| title_fullStr | On two problems in graph Ramsey theory |
| title_full_unstemmed | On two problems in graph Ramsey theory |
| title_short | On two problems in graph Ramsey theory |
| title_sort | on two problems in graph ramsey theory |
| url | http://hdl.handle.net/1721.1/71250 |
| work_keys_str_mv | AT conlondavid ontwoproblemsingraphramseytheory AT foxjacob ontwoproblemsingraphramseytheory AT sudakovbenny ontwoproblemsingraphramseytheory |