Mathematica Bohemica, Vol. 146, No. 2, pp. 229-234, 2021
A note on the size Ramsey numbers for matchings versus cycles
Edy Tri Baskoro, Tomáš Vetrík
Received December 30, 2018. Published online June 2, 2020.
Abstract: 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 \ge2$ 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 \ge12$ and $\hat{r} (3K_2, C_n) < n + 6 \sqrt{n} + 9$ for $n \ge25$.
References: [1] Effendi, B. Ginting, Surahmat, Dafik, S. Sy: The size multipartite Ramsey numbers of large paths versus small graph. Far East J. Math. Sci. (FJMS) 102 (2017), 507-514. DOI 10.17654/MS102030507 | Zbl 1378.05125
[2] P. Erdős, R. J. Faudree: Size Ramsey numbers involving matchings. Finite and Infinite Sets. Vol. I, II (Eger, 1981) (A. Hajnal et al., eds.). Colloquia Mathematica Societatis János Bolyai 37. János Bolyai Mathematical Society, Budapest; North-Holland, Amsterdam (1984), 247-264. DOI 10.1016/B978-0-444-86893-0.50019-X | MR 0818238 | Zbl 0563.05043
[3] P. Erdős, R. J. Faudree, C. C. Rousseau, R. H. Schelp: The size Ramsey number. Period. Math. Hung. 9 (1978), 145-161. DOI 10.1007/BF02018930 | MR 0479691 | Zbl 0331.05122
[4] R. J. Faudree, J. Sheehan: Size Ramsey numbers for small-order graphs. J. Graph Theory 7 (1983), 53-55. DOI 10.1002/jgt.3190070107 | MR 0693020 | Zbl 0505.05043
[5] X. Ke: The size Ramsey number of trees with bounded degree. Random Struct. Algorithms 4 (1993), 85-97. DOI 10.1002/rsa.3240040106 | MR 1192528 | Zbl 0778.05060
[6] R. Lortz, I. Mengersen: Size Ramsey results for paths versus stars. Australas. J. Comb. 18 (1998), 3-12. MR 1658352 | Zbl 0914.05053
[7] P. H. Perondi, E. L. Monte Carmelo: Set and size multipartite Ramsey numbers for stars. Discrete Appl. Math. 250 (2018), 368-372. DOI 10.1016/j.dam.2018.05.016 | MR 3868682 | Zbl 1398.05131
Affiliations: Edy Tri Baskoro, Institut Teknologi Bandung, Combinatorial Mathematics Research Group, Faculty of Mathematics and Natural Sciences, Jl. Ganesa 10, Bandung, Jawa Barat, Indonesia, e-mail: ebaskoro@math.itb.ac.id; Tomáš Vetrík, University of the Free State, Department of Mathematics and Applied Mathematics, 205 Nelson Mandela Drive, Park West, Bloemfontein, 9301, South Africa, e-mail: vetrikt@ufs.ac.za
