no. 12 · Tuesday 10 November 2026
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\ge4$, the best-known asymptotic 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 $\left(k+o(1)\right)n$ to $\left(\frac{k+3}{3}+o(1)\right)n$ as $n\to\infty$.
- fields
- Combinatorics