UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Ramsey goodness of cycles

Pokrovskiy, A; Sudakov, B; (2020) Ramsey goodness of cycles. SIAM Journal on Discrete Mathematics , 34 (3) pp. 1884-1908. 10.1137/18M1199125. Green open access

[img]
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 > 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
Downloads since deposit
7Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item