Size-Ramsey numbers of cycles versus a path

Abstract

The size-Ramsey number $\hat{R}(\mathcal{F},H)$ of a family of graphs $\mathcal{F}$ and a graph $H$ is the smallest integer $m$ such that there exists a graph $G$ on $m$ edges with the property that any colouring of the edges of $G$ with two colours, say, red and blue, yields a red copy of a graph from $\mathcal{F}$ or a blue copy of $H$. In this paper we first focus on $\mathcal{F}={\mathcal{C}}_{\le cn}$, where ${\mathcal{C}}_{\le cn}$ is the family of cycles of length at most $cn$, and $H=P_n$. In particular, we show that $2.00365n\le \hat{R}({\mathcal{C}}_{\le n},P_n)\le 31n$. Using similar techniques, we also managed to analyze $\hat{R}(C_n,P_n)$, which was investigated before but only using the regularity method.

arXiv admin note: text overlap with arXiv:1601.02564