Connected Counterexamples for Target Ramsey Numbers

Abstract

Chartrand and Zhang asked whether there exists a graph $G$ without isolated vertices whose target Ramsey number satisfies $\mathrm{TR}(G)>\mathrm{R}(G)$. We answer the question affirmatively, even under strong structural restrictions. If ${\Gamma }_t=P_t\square P_t$ is the square $t\times t$ grid, then the elementary counting bound of Chartrand and Zhang gives $\mathrm{TR}({\Gamma }_t)\ge 2t(t-1)+1$, whereas a theorem of Mota, Sarkozy, Schacht and Taraz gives $\mathrm{R}({\Gamma }_t)=(3/2+o(1))t^2$. Consequently, $\mathrm{TR}({\Gamma }_t)>\mathrm{R}({\Gamma }_t)$ for all sufficiently large $t$, so there are infinitely many connected, planar, bipartite counterexamples of maximum degree four. Higher-dimensional grids show that the ratio $\mathrm{TR}(G)/\mathrm{R}(G)$ is unbounded on connected bipartite graphs, while each fixed-dimensional witnessing family has bounded maximum degree. We also record an independent construction of disconnected counterexamples from the theorem of Burr, Erdos and Spencer on Ramsey numbers of multiple copies: if a fixed graph $H$ satisfies $e(H)>2v(H)-\alpha (H)$, then $\mathrm{TR}(qH)>\mathrm{R}(qH)$ for every sufficiently large $q$.

6 pages. Answers a question of Chartrand and Zhang on target Ramsey numbers