Ramsey numbers of cycles versus general graphs
The Ramsey number R(F, H) is the minimum number N such that any N-vertex graph either contains a copy of F or its complement contains H. Burr in 1981 proved a pleasingly general result that for any graph H, provided n is sufficiently large, a natural lower bound construction gives the correct Ramsey...
| Główni autorzy: | , , , |
|---|---|
| Format: | Journal article |
| Język: | English |
| Wydane: |
Cambridge University Press
2023
|
| _version_ | 1826309652322713600 |
|---|---|
| author | Haslegrave, J Hyde, J Kim, J Liu, H |
| author_facet | Haslegrave, J Hyde, J Kim, J Liu, H |
| author_sort | Haslegrave, J |
| collection | OXFORD |
| description | The Ramsey number R(F, H) is the minimum number N such that any N-vertex graph
either contains a copy of F or its complement contains H. Burr in 1981 proved a pleasingly
general result that for any graph H, provided n is sufficiently large, a natural lower bound
construction gives the correct Ramsey number involving cycles: R(Cn, H) = (n−1)(χ(H)−
1) + σ(H), where σ(H) is the minimum possible size of a colour class in a χ(H)-colouring
of H. Allen, Brightwell and Skokan conjectured that the same should be true already when
n ≥ |H|χ(H).
We improve this 40-year-old result of Burr by giving quantitative bounds of the form
n ≥ C|H| log4
χ(H), which is optimal up to the logarithmic factor. In particular, this
proves a strengthening of the Allen-Brightwell-Skokan conjecture for all graphs H with
large chromatic number. |
| first_indexed | 2024-03-07T07:37:29Z |
| format | Journal article |
| id | oxford-uuid:1da30f15-9e45-495e-839f-1060f0adab15 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T07:37:29Z |
| publishDate | 2023 |
| publisher | Cambridge University Press |
| record_format | dspace |
| spelling | oxford-uuid:1da30f15-9e45-495e-839f-1060f0adab152023-04-03T10:01:14ZRamsey numbers of cycles versus general graphsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:1da30f15-9e45-495e-839f-1060f0adab15EnglishSymplectic ElementsCambridge University Press2023Haslegrave, JHyde, JKim, JLiu, HThe Ramsey number R(F, H) is the minimum number N such that any N-vertex graph either contains a copy of F or its complement contains H. Burr in 1981 proved a pleasingly general result that for any graph H, provided n is sufficiently large, a natural lower bound construction gives the correct Ramsey number involving cycles: R(Cn, H) = (n−1)(χ(H)− 1) + σ(H), where σ(H) is the minimum possible size of a colour class in a χ(H)-colouring of H. Allen, Brightwell and Skokan conjectured that the same should be true already when n ≥ |H|χ(H). We improve this 40-year-old result of Burr by giving quantitative bounds of the form n ≥ C|H| log4 χ(H), which is optimal up to the logarithmic factor. In particular, this proves a strengthening of the Allen-Brightwell-Skokan conjecture for all graphs H with large chromatic number. |
| spellingShingle | Haslegrave, J Hyde, J Kim, J Liu, H Ramsey numbers of cycles versus general graphs |
| title | Ramsey numbers of cycles versus general graphs |
| title_full | Ramsey numbers of cycles versus general graphs |
| title_fullStr | Ramsey numbers of cycles versus general graphs |
| title_full_unstemmed | Ramsey numbers of cycles versus general graphs |
| title_short | Ramsey numbers of cycles versus general graphs |
| title_sort | ramsey numbers of cycles versus general graphs |
| work_keys_str_mv | AT haslegravej ramseynumbersofcyclesversusgeneralgraphs AT hydej ramseynumbersofcyclesversusgeneralgraphs AT kimj ramseynumbersofcyclesversusgeneralgraphs AT liuh ramseynumbersofcyclesversusgeneralgraphs |