On the asymptotic behavior of online Ramsey numbers for stars, paths and cycles

Abstract

The online Ramsey game for graphs $G$ and $H$ is played on the infinite complete graph $K_{\mathbb{N}}$. Each round, Builder chooses an edge, and Painter colors it red or blue. The online Ramsey number $\tilde{r}(G,H)$ is the smallest integer $t$ for which Builder has a strategy that guarantees a red copy of $G$ or a blue copy of $H$ in at most $t$ rounds. We show that for every fixed $k$, there are constants ${\lambda }_1$ and ${\lambda }_2$ such that $\tilde{r}(P_k,P_n)/n$ and $\tilde{r}(P_k,C_n)/n$ converge to ${\lambda }_1$, and $\tilde{r}(K_{1,k},P_n)/n$ and $\tilde{r}(K_{1,k},C_n)/n$ converge to ${\lambda }_2$.

v2 contains additional results on stars vs paths and cycles