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

Cité par Sources :