Size Ramsey numbers of stars versus cliques

Abstract

The size Ramsey number $\hat{r}(G,H)$ of two graphs $G$ and $H$ is the smallest integer $m$ such that there exists a graph $F$ on $m$ edges with the property that every red-blue colouring of the edges of $F$, yields a red copy of $G$ or a blue copy of $H$. In $1981$, Erdős observed that $\hat{r}(K_{1,k},K_3)\le \left(\genfrac{}{}{0ex}{}{2k+1}{2}\right)-\left(\genfrac{}{}{0ex}{}{k}{2}\right)$ and he conjectured that the corresponding upper bound on $\hat{r}(K_{1,k},K_3)$ is sharp. In $1983$, Faudree and Sheehan extended this conjecture as follows: \hat{r}(K_{1,k},K_{n})=\left \{ {lr} \binom{k(n-1)+1}{2}-\binom{k}{2} & ~k\geq n~ \text{or}~ k~ \text{odd}. \binom{k(n-1)+1}{2}-k(n-1)/2 & \text{otherwise}. \right. They proved the case $k=2$. In $2001$, Pikhurko showed that this conjecture is not true for $n=3$ and $k\ge 5$, disproving the mentioned conjecture of Erdős. Here we prove Faudree and Sheehan's conjecture for a given $k\ge 2$ and $n\ge k^3+2k^2+2k$.