Asymptotic Bounds for Online Ramsey Numbers of Stars versus Long Paths and Cycles

Abstract

The online Ramsey game for graphs $G$ and $H$ is played on the infinite complete graph $K_{\mathbb{N}}$. In 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 guaranteeing a red copy of $G$ or a blue copy of $H$ within $t$ rounds. For every fixed integer $k\ge 4$, the best-known lower bounds for $\tilde{r}(K_{1,k},P_n)$ and $\tilde{r}(K_{1,k},C_n)$ are $\left(\frac{k+3}{4}+o(1)\right)n$ as $n\to \infty$. We improve the corresponding asymptotic upper bounds from $(k+o(1))n$ to $\left(\frac{2k+4}{5}+o(1)\right)n$ as $n\to \infty$.