Globally sparse vertex‐ramsey graphs

For graphs G and F we write F → ( G ) 1 r if every r ‐coloring of the vertices of F results in a monochromatic copy of G . The global density m ( F ) of F is the maximum ratio of the number of edges to the number of vertices taken over all subgraphs of F . Let\documentclass{article}\pagestyle{empty}\begin{document}$$ m_{cr} \left({G,\,r} \right) = \inf \left\{{m\left(F \right):\,F \to \left(G \right)_r^1 } \right\}. $$\end{document}We show that\documentclass{article}\pagestyle{empty}\begin{document}$$ \frac{1}{2} \le \frac{{m_{cr} \left({G,\,r} \right)}}{{r\,\max _{H \subseteq G} \delta \left(H \right)}} < \,1. $$\end{document}The lower bound is achieved by complete graphs, whereas, for all r ≥ 2 and ϵ > 0, m cr ( S k , r ) > r ‐ ϵ for sufficiently large k , where S k is the star with k arms. In particular, we prove that\documentclass{article}\pagestyle{empty}\begin{document}$$ \frac{4}{3} \le \,m_{cr} \left({S_2,\,2} \right) \le \,\frac{7}{5}. $$\end{document}