Geodesic
A note on the size Ramsey numbers for matchings versus cycles
Mathematica Bohemica, Tome 146 (2021) no. 2, pp. 229-234
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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$.
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$.
DOI : 10.21136/MB.2020.0174-18
Classification : 05C35, 05C55
Keywords: size Ramsey number; matching; cycle 
@article{10_21136_MB_2020_0174_18,
     author = {Baskoro, Edy Tri and Vetr{\'\i}k, Tom\'a\v{s}},
     title = {A note on the size {Ramsey} numbers for matchings versus cycles},
     journal = {Mathematica Bohemica},
     pages = {229--234},
     year = {2021},
     volume = {146},
     number = {2},
     doi = {10.21136/MB.2020.0174-18},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/MB.2020.0174-18/}
}
TY  - JOUR
AU  - Baskoro, Edy Tri
AU  - Vetrík, Tomáš
TI  - A note on the size Ramsey numbers for matchings versus cycles
JO  - Mathematica Bohemica
PY  - 2021
SP  - 229
EP  - 234
VL  - 146
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.21136/MB.2020.0174-18/
DO  - 10.21136/MB.2020.0174-18
LA  - en
ID  - 10_21136_MB_2020_0174_18
ER  - 
%0 Journal Article
%A Baskoro, Edy Tri
%A Vetrík, Tomáš
%T A note on the size Ramsey numbers for matchings versus cycles
%J Mathematica Bohemica
%D 2021
%P 229-234
%V 146
%N 2
%U http://geodesic.mathdoc.fr/articles/10.21136/MB.2020.0174-18/
%R 10.21136/MB.2020.0174-18
%G en
%F 10_21136_MB_2020_0174_18
Baskoro, Edy Tri; Vetrík, Tomáš. A note on the size Ramsey numbers for matchings versus cycles. Mathematica Bohemica, Tome 146 (2021) no. 2, pp. 229-234. doi: 10.21136/MB.2020.0174-18

[1] Effendi, Ginting, B., Surahmat, Dafik, Sy, S.: The size multipartite Ramsey numbers of large paths versus small graph. Far East J. Math. Sci. (FJMS) 102 (2017), 507-514. | DOI | JFM

[2] Erdős, P., Faudree, R. J.: Size Ramsey numbers involving matchings. Finite and Infinite Sets. Vol. I, II (Eger, 1981) Colloquia Mathematica Societatis János Bolyai 37. János Bolyai Mathematical Society, Budapest; North-Holland, Amsterdam (1984), 247-264 A. Hajnal et al. | DOI | MR | JFM

[3] Erdős, P., Faudree, R. J., Rousseau, C. C., Schelp, R. H.: The size Ramsey number. Period. Math. Hung. 9 (1978), 145-161. | DOI | MR | JFM

[4] Faudree, R. J., Sheehan, J.: Size Ramsey numbers for small-order graphs. J. Graph Theory 7 (1983), 53-55. | DOI | MR | JFM

[5] Ke, X.: The size Ramsey number of trees with bounded degree. Random Struct. Algorithms 4 (1993), 85-97. | DOI | MR | JFM

[6] Lortz, R., Mengersen, I.: Size Ramsey results for paths versus stars. Australas. J. Comb. 18 (1998), 3-12. | MR | JFM

[7] Perondi, P. H., Carmelo, E. L. Monte: Set and size multipartite Ramsey numbers for stars. Discrete Appl. Math. 250 (2018), 368-372. | DOI | MR | JFM

Cité par Sources :