On a question of Erdos and Faudree on the size Ramsey numbers

Abstract

For given simple graphs $G_1$ and $G_2$, the size Ramsey number $\hat{R}(G_1,G_2)$ is the smallest positive integer $m$, where there exists a graph $G$ with $m$ edges such that in any edge coloring of $G$ with two colors red and blue, there is either a red copy of $G_1$ or a blue copy of $G_2$. In 1981, Erdős and Faudree investigated the size Ramsey number $\hat{R}(K_n,t{K}_2)$, where $K_n$ is a complete graph on $n$ vertices and $t{K}_2$ is a matching of size $t$. They obtained the value of $\hat{R}(K_n,t{K}_2)$ when $n\ge 4t-1$ as well as for $t=2$ and asked for the behavior of these numbers when $t$ is much larger than $n$. In this regard, they posed the following interesting question: For every positive integer $n$, is it true that $$\underset{t\to \infty }{\lim }\frac{\hat{R}(K_n,t{K}_2)}{t\hat{R}(K_n,K_2)}=\min \left\{\frac{\left(\genfrac{}{}{0ex}{}{n+2t-2}{2}\right)}{t\left(\genfrac{}{}{0ex}{}{n}{2}\right)}\mid t\in \mathbb{N}\right\}?$$ In this paper, we obtain the exact value of $\hat{R}(K_n,t{K}_2)$ for every positive integers $n,t$ and as a byproduct, we give an affirmative answer to the question of Erdős and Faudree.

11 pages