Online size Ramsey numbers: Odd cycles vs connected graphs

Abstract

Given two graph families ${\mathcal{H}}_1$ and ${\mathcal{H}}_2$, a size Ramsey game is played on the edge set of $K_{\mathbb{N}}$. In every round, Builder selects an edge and Painter colours it red or blue. Builder is trying to force Painter to create as soon as possible a red copy of a graph from ${\mathcal{H}}_1$ or a blue copy of a graph from ${\mathcal{H}}_2$. The online (size) Ramsey number $\tilde{r}({\mathcal{H}}_1,{\mathcal{H}}_2)$ is the smallest number of rounds in the game provided Builder and Painter play optimally. We prove that if ${\mathcal{H}}_1$ is the family of all odd cycles and ${\mathcal{H}}_2$ is the family of all connected graphs on $n$ vertices and $m$ edges, then $\tilde{r}({\mathcal{H}}_1,{\mathcal{H}}_2)\ge \phi n+m-2\phi +1$, where $\phi$ is the golden ratio, and for $n\ge 3$, $m\le (n-1{)}^2/4$ we have $\tilde{r}({\mathcal{H}}_1,{\mathcal{H}}_2)\le n+2m+O(\sqrt{m-n+1})$. We also show that $\tilde{r}(C_3,P_n)\le 3n-4$ for $n\ge 3$. As a consequence we get $2.6n-3\le \tilde{r}(C_3,P_n)\le 3n-4$ for every $n\ge 3$.

14 pages, 0 figures; added appendix containing intuition behind the potential function used for lower bound; corrected typos and added a few clarifications