Asymptotic Bounds for Online Ramsey Numbers of Stars versus Long Paths and Cycles
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 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$…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.27405
curl -X POST /api/v1/records/arxiv/2608.27405/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.27405/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'