On the Ramsey numbers of fans and stars

Abstract

Let $F_n$ be the graph on $2n+1$ vertices consisting of $n$ triangles meeting at a single vertex. After a number of improvements over the years, it is currently known that the Ramsey number of $F_n$ is between $4.5n-5$ (Chen, Yu, Zhao) and $(5+\frac{1}{6})n+O(1)$ (Dvo{ř}{á}k and Metrebian). We improve both of these bounds as follows $$4.732n\approx (3+\sqrt{3})n-8<R(F_n)\le (5+o(1))n.$$ Additionally, as it relates to the lower bound on $R(F_n)$ (and for which nothing was known when $n<m<n(n-1)$), we determine the Ramsey numbers of stars vs.~fans, within a constant, as follows $$R(K_{1,m},F_n)=\{\begin{array}{llc}m+2n-\frac{1+(-1{)}^m}{2},& m\le n\frac{3m+\sqrt{m^2+8n^2}}{2}+\Theta (1),& m>n\end{array}.$$ In particular, we have $R(K_{1,2n},F_n)=(3+\sqrt{3})n+\Theta (1)$.

28 pages (plus 2 page appendix), 5 figures