A note on the size Ramsey numbers for matchings versus cycles

Baskoro, Edy Tri ; Vetrík, Tomáš

Mathematica Bohemica, Tome 146 (2021) no. 2, pp. 229-234.

Résumé

For graphs $G$, $F_1$, $F_2$, we write $G \rightarrow (F_1, F_2)$ if for every red-blue colouring of the edge set of $G$ we have a red copy of $F_1$ or a blue copy of $F_2$ in $G$. The size Ramsey number $\hat {r}(F_1, F_2)$ is the minimum number of edges of a graph $G$ such that $G \rightarrow (F_1, F_2)$. Erdős and Faudree proved that for the cycle $C_n$ of length $n$ and for $t \ge 2$ matchings $tK_2$, the size Ramsey number $\hat {r} (tK_2, C_n) n + (4t+3) \sqrt {n}$. We improve their upper bound for $t = 2$ and $t=3$ by showing that $\hat {r} (2K_2, C_n) \le n + 2 \sqrt {3n} + 9$ for $n \ge 12$ and $\hat {r} (3K_2, C_n) n + 6 \sqrt {n} + 9$ for $n \ge 25$.

Détail

DOI : 10.21136/MB.2020.0174-18

Classification : 05C35, 05C55
Keywords: size Ramsey number; matching; cycle