Size Ramsey numbers of stars versus cliques

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})\leq \binom{2k+1}{2}-\binom{k}{2}$ 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\geq 5$, disproving the mentioned conjecture of Erdős. Here we prove Faudree and Sheehan's conjecture for a given $k\geq 2$ and $n\geq k^{3}+2k^{2}+2k$.

No reviews yet.

No comments yet.