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.
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 |
Archive Staff Only
View Item |