Lower bounds for online size Ramsey numbers for paths
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916699338440704 |
|---|---|
| author | Adamska, Natalia Adamski, Grzegorz |
| author_facet | Adamska, Natalia Adamski, Grzegorz |
| contents | Given two graphs $H_1$ and $H_2$, an online Ramsey game is played on the edge set of $K_\mathbb{N}$. In every round Builder selects an edge and Painter colors it red or blue. Builder is trying to force Painter to create a red copy of $H_1$ or a blue copy of $H_2$ as soon as possible, while Painter's goal is the opposite. The online (size) Ramsey number $\tilde{r}(H_1,H_2)$ is the smallest number of rounds in the game provided Builder and Painter play optimally. Let $v(G)$ be the number of vertices in the graph $G$ and $v_1(G)$ be the number of vertices of degree 1 in $G$. We prove that if $G$ has no isolated vertices, then $\tilde{r}(P_7,G)\ge 8v(G)/5-v_1(G)$, $\tilde{r}(P_8,G)\ge 18v(G)/11-v_1(G)$ and $\tilde{r}(P_9,G)\ge 5v(G)/3-v_1(G)$. In particular $\tilde{r}(P_9,P_n)\ge 5n/3-2,$ which with known upper bound implies $\lim_{n\to\infty} \tilde{r}(P_9,P_n)/n=5/3.$ We also show that for any fixed $k$, $\lim_{n\to\infty} \tilde{r}(P_k,P_n)/n$ exists. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_14926 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Lower bounds for online size Ramsey numbers for paths Adamska, Natalia Adamski, Grzegorz Combinatorics 05C55, 05C57, 91A46 Given two graphs $H_1$ and $H_2$, an online Ramsey game is played on the edge set of $K_\mathbb{N}$. In every round Builder selects an edge and Painter colors it red or blue. Builder is trying to force Painter to create a red copy of $H_1$ or a blue copy of $H_2$ as soon as possible, while Painter's goal is the opposite. The online (size) Ramsey number $\tilde{r}(H_1,H_2)$ is the smallest number of rounds in the game provided Builder and Painter play optimally. Let $v(G)$ be the number of vertices in the graph $G$ and $v_1(G)$ be the number of vertices of degree 1 in $G$. We prove that if $G$ has no isolated vertices, then $\tilde{r}(P_7,G)\ge 8v(G)/5-v_1(G)$, $\tilde{r}(P_8,G)\ge 18v(G)/11-v_1(G)$ and $\tilde{r}(P_9,G)\ge 5v(G)/3-v_1(G)$. In particular $\tilde{r}(P_9,P_n)\ge 5n/3-2,$ which with known upper bound implies $\lim_{n\to\infty} \tilde{r}(P_9,P_n)/n=5/3.$ We also show that for any fixed $k$, $\lim_{n\to\infty} \tilde{r}(P_k,P_n)/n$ exists. |
| title | Lower bounds for online size Ramsey numbers for paths |
| topic | Combinatorics 05C55, 05C57, 91A46 |
| url | https://arxiv.org/abs/2504.14926 |