On the size-Ramsey number of cycles

• Published in: arXiv.org 2017-01
• Main Authors: Javadi, Ramin, Khoeini, Farideh, Omidi, Gholam Reza, Pokrovskiy, Alexey
• Format: Article
• Language: English
• Subjects: Graph coloring; Graph theory; Regularity; Upper bounds
• ISSN: 2331-8422

For given graphs \(G_1,\ldots,G_k\), the size-Ramsey number \(\hat{R}(G_1,\ldots,G_k)\) 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,\ldots,k\), \( H \) contains a monochromatic copy of \(G_i\) of color \(i\) for some \(1\leq i\leq k\). We denote \(\hat{R}(G_1,\ldots,G_k)\) by \(\hat{R}_{k}(G)\) when \(G_1=\cdots=G_k=G\). Haxell, Kohayakawa and \L{}uczak showed that the size Ramsey number of a cycle \(C_n\) is linear in \(n\) i.e. \(\hat{R}_{k}(C_{n})\leq c_k n\) for some constant \(c_k\). Their proof, is based on the regularity lemma of Szemer\'{e}di and so no specific constant \(c_k\) is known. In this paper, we give various upper bounds for the size-Ramsey numbers of cycles. We give an alternative proof of \(\hat{R}_{k}(C_{n})\leq c_k n\), avoiding the use of the regularity lemma. For two colours, we show that for sufficiently large \(n\) we have \(\hat{R}(C_{n},C_{n}) \leq 10^6\times cn,\) where \(c=843\) if \(n\) is even and \(c=113482\) otherwise.