Size Ramsey numbers of stars versus 3-chromatic graphs (Q5955210)

Write \(G\rightarrow(F_1,F_2)\) if any blue-red colouring of the edges of the graph \(G\) produces either a blue copy of \(F_1\) or a red copy of \(F_2\). The size Ramsey number \(\hat{r}(F_1,F_2)\) is the minimal number of edges of a graph \(G\) such that \(G\rightarrow(F_1,F_2)\). More generally, we could replace \(F_2\), say, by a class of graphs and ask that any colouring yield at least one red copy of a member of that class. The main result of this paper can now be stated as \[ n^2+(0.577+o(1))n^{3/2} < \hat{r}(K_{1,n},C) \leq \hat{r}(K_{1,n},K_3) < n^2+\sqrt{2}n^{3/2}+n, \] where \(C\) is the family of all odd cycles, \(K_{1,n}\) is a star with \(n\) edges and \(K_3\) is a 3-cycle. The upper bound disproves a conjecture by Erdős that \(\hat{r}(K_{1,n},K_3)={2n+1\choose 2}-{n\choose 2}\). The construction on which this upper bound is based is used to show that in fact \(\hat{r}(K_{1,n},F)=(1+o(1))n^2\) for any given 3-chromatic graph \(F\).