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

On the Size-Ramsey Number of Cycles

Javadi, R; Khoeini, F; Omidi, GR; Pokrovskiy, A; (2019) On the Size-Ramsey Number of Cycles. Combinatorics, Probability and Computing , 28 (6) pp. 871-880. 10.1017/S0963548319000221. Green open access

[thumbnail of SRC-2019-2-3.pdf]
Preview
Text
SRC-2019-2-3.pdf - Accepted Version

Download (284kB) | Preview

Abstract

For given graphs G1, . . . , Gk, the size-Ramsey number Rˆ(G1, . . . , Gk) is the smallest integer m for which there exists a graph H on m edges such that in every k-edge coloring of H with colors 1, . . . , k, H contains a monochromatic copy of Gi of color i for some 1 ≤ i ≤ k. We denote Rˆ(G1, . . . , Gk) by Rˆ k(G) when G1 = · · · = Gk = G. Haxell, Kohayakawa and Luczak showed that the size-Ramsey number of a cycle Cn is linear in n i.e. Rˆ k(Cn) ≤ ckn for some constant ck. Their proof, however, is based on the regularity lemma of Szemer´edi and so no specific constant ck is known. In this paper, we give various upper bounds for the size-Ramsey numbers of cycles. We provide an alternative proof of Rˆ k(Cn) ≤ ckn, avoiding the use of the regularity lemma, where ck is exponential and doubly-exponential in k, when n is even and odd, respectively. In particular, we show that for sufficiently large n we have Rˆ 2(Cn) ≤ 105 × cn, where c = 6.5 if n is even and c = 1989 otherwise.

Type: Article
Title: On the Size-Ramsey Number of Cycles
Open access status: An open access version is available from UCL Discovery
DOI: 10.1017/S0963548319000221
Publisher version: https://doi.org/10.1017/S0963548319000221
Language: English
Additional information: This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions.
Keywords: Ramsey number, Size Ramsey number, Random graphs, Cycles
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/10112642
Downloads since deposit
44Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item