On two problems in graph Ramsey theory
<p>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. </p><p>The Ramsey number <i>r</i>(<i>H</i>...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Published: |
Springer Verlag
2012
|
| _version_ | 1826257858306506752 |
|---|---|
| author | Conlon, D Fox, J Sudakov, B |
| author_facet | Conlon, D Fox, J Sudakov, B |
| author_sort | Conlon, D |
| collection | OXFORD |
| description | <p>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. </p><p>The Ramsey number <i>r</i>(<i>H</i>) of a graph <i>H</i> is the least positive integer <i>N</i> such that every two-coloring of the edges of the complete graph <i>K</i><sub><i>N</i></sub> contains a monochromatic copy of <i>H</i>. A famous result of Chváatal, Rödl, Szemerédi and Trotter states that there exists a constant <i>c</i>(<i>Δ</i>) such that <i>r</i>(<i>H</i>) ≤ <i>c</i>(<i>Δ</i>)<i>n</i> for every graph <i>H</i> with <i>n</i> vertices and maximum degree <i>Δ</i>. The important open question is to determine the constant <i>c</i>(<i>Δ</i>). The best results, both due to Graham, Rödl and Ruciński, state that there are positive constants <i>c</i> and <i>c′</i> such that 2<sup><i>c′Δ</i></sup> ≤ <i>c</i>(<i>Δ</i>) ≤ <sup><i>cΔ</i>log<sup>2</sup><i>Δ</i></sup>. We improve this upper bound, showing that there is a constant <i>c</i> for which <i>c</i>(<i>Δ</i>) ≤ 2<sup><i>cΔ</i>log<i>Δ</i></sup>. </p><p>The induced Ramsey number <i>r</i><sub><i>ind</i></sub>(<i>H</i>) of a graph <i>H</i> is the least positive integer <i>N</i> for which there exists a graph <i>G</i> on <i>N</i> vertices such that every two-coloring of the edges of <i>G</i> contains an induced monochromatic copy of <i>H</i>. Erdős conjectured the existence of a constant <i>c</i> such that, for any graph <i>H</i> on <i>n</i> vertices, <i>r</i><sub><i>ind</i></sub>(<i>H</i>) ≤ 2<sup><i>cn</i></sup>. We move a step closer to proving this conjecture, showing that <i>r</i><sub><i>ind</i></sub>(<i>H</i>) ≤ 2<sup><i>cn</i>log<i>n</i></sup>. This improves upon an earlier result of Kohayakawa, Prömel and Rödl by a factor of log<i>n</i> in the exponent.</p> |
| first_indexed | 2024-03-06T18:24:49Z |
| format | Journal article |
| id | oxford-uuid:07950dc1-8ac3-4cb1-810e-154ec6e4c93b |
| institution | University of Oxford |
| last_indexed | 2024-03-06T18:24:49Z |
| publishDate | 2012 |
| publisher | Springer Verlag |
| record_format | dspace |
| spelling | oxford-uuid:07950dc1-8ac3-4cb1-810e-154ec6e4c93b2022-03-26T09:08:21ZOn two problems in graph Ramsey theoryJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:07950dc1-8ac3-4cb1-810e-154ec6e4c93bSymplectic Elements at OxfordSpringer Verlag2012Conlon, DFox, JSudakov, B <p>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. </p><p>The Ramsey number <i>r</i>(<i>H</i>) of a graph <i>H</i> is the least positive integer <i>N</i> such that every two-coloring of the edges of the complete graph <i>K</i><sub><i>N</i></sub> contains a monochromatic copy of <i>H</i>. A famous result of Chváatal, Rödl, Szemerédi and Trotter states that there exists a constant <i>c</i>(<i>Δ</i>) such that <i>r</i>(<i>H</i>) ≤ <i>c</i>(<i>Δ</i>)<i>n</i> for every graph <i>H</i> with <i>n</i> vertices and maximum degree <i>Δ</i>. The important open question is to determine the constant <i>c</i>(<i>Δ</i>). The best results, both due to Graham, Rödl and Ruciński, state that there are positive constants <i>c</i> and <i>c′</i> such that 2<sup><i>c′Δ</i></sup> ≤ <i>c</i>(<i>Δ</i>) ≤ <sup><i>cΔ</i>log<sup>2</sup><i>Δ</i></sup>. We improve this upper bound, showing that there is a constant <i>c</i> for which <i>c</i>(<i>Δ</i>) ≤ 2<sup><i>cΔ</i>log<i>Δ</i></sup>. </p><p>The induced Ramsey number <i>r</i><sub><i>ind</i></sub>(<i>H</i>) of a graph <i>H</i> is the least positive integer <i>N</i> for which there exists a graph <i>G</i> on <i>N</i> vertices such that every two-coloring of the edges of <i>G</i> contains an induced monochromatic copy of <i>H</i>. Erdős conjectured the existence of a constant <i>c</i> such that, for any graph <i>H</i> on <i>n</i> vertices, <i>r</i><sub><i>ind</i></sub>(<i>H</i>) ≤ 2<sup><i>cn</i></sup>. We move a step closer to proving this conjecture, showing that <i>r</i><sub><i>ind</i></sub>(<i>H</i>) ≤ 2<sup><i>cn</i>log<i>n</i></sup>. This improves upon an earlier result of Kohayakawa, Prömel and Rödl by a factor of log<i>n</i> in the exponent.</p> |
| spellingShingle | Conlon, D Fox, J Sudakov, B 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 |
| work_keys_str_mv | AT conlond ontwoproblemsingraphramseytheory AT foxj ontwoproblemsingraphramseytheory AT sudakovb ontwoproblemsingraphramseytheory |