On the asymptotic behavior of online Ramsey numbers for stars, paths and cycles
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915945442705408 |
|---|---|
| author | Beilis, Sam Curbelo, Israel R. |
| author_facet | Beilis, Sam Curbelo, Israel R. |
| contents | 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 $λ_1$ and $λ_2$ such that $\tilde{r}(P_k,P_n)/n$ and $\tilde{r}(P_k,C_n)/n$ converge to $λ_1$, and $\tilde{r}(K_{1,k},P_n)/n$ and $\tilde{r}(K_{1,k},C_n)/n$ converge to $λ_2$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_15643 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On the asymptotic behavior of online Ramsey numbers for stars, paths and cycles Beilis, Sam Curbelo, Israel R. Combinatorics Discrete Mathematics 05D10 G.2.2 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 $λ_1$ and $λ_2$ such that $\tilde{r}(P_k,P_n)/n$ and $\tilde{r}(P_k,C_n)/n$ converge to $λ_1$, and $\tilde{r}(K_{1,k},P_n)/n$ and $\tilde{r}(K_{1,k},C_n)/n$ converge to $λ_2$. |
| title | On the asymptotic behavior of online Ramsey numbers for stars, paths and cycles |
| topic | Combinatorics Discrete Mathematics 05D10 G.2.2 |
| url | https://arxiv.org/abs/2604.15643 |