Pokrovskiy, A;
Sudakov, B;
(2020)
Ramsey goodness of cycles.
SIAM Journal on Discrete Mathematics
, 34
(3)
pp. 1884-1908.
10.1137/18M1199125.
Preview |
Text
18m1199125.pdf - Published Version Download (645kB) | Preview |
Abstract
Given a pair of graphs G and H, the Ramsey number R(G, H) is the smallest N such that every red-blue coloring of the edges of the complete graph KN contains a red copy of G or a blue copy of H. If a graph G is connected, it is well known and easy to show that R(G, H) \geq (| G| - 1)(\chi (H) - 1) + \sigma (H), where \chi (H) is the chromatic number of H and \sigma (H) is the size of the smallest color class in a \chi (H)-coloring of H. A graph G is called H-good if R(G, H) = (| G| - 1)(\chi (H) - 1) + \sigma (H). The notion of Ramsey goodness was introduced by Burr and Erd\H os in 1983 and has been extensively studied since then. In this paper we show that if n \geq 1060| H| and \sigma (H) \geq \chi (H) 22, then the n-vertex cycle Cn is H-good. For graphs H with high \chi (H) and \sigma (H), this proves in a strong form a conjecture of Allen, Brightwell, and Skokan.
| Type: | Article |
|---|---|
| Title: | Ramsey goodness of cycles |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1137/18M1199125 |
| Publisher version: | https://doi.org/10.1137/18M1199125 |
| Language: | English |
| Additional information: | This version is the version of record. For information on re-use, please refer to the publisher’s terms and conditions. |
| Keywords: | Ramsey theory, cycles, expanders |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10109779 |
Archive Staff Only
 |
View Item |
