Online size Ramsey numbers: odd cycles vs connected graphs

Grzegorz Adamski¹ ; Małgorzata Bednarska-Bzdęga¹

¹Adam Mickiewicz University, Poznań

The electronic journal of combinatorics, Tome 31 (2024) no. 3

Résumé

Given two graph families $\mathcal H_1$ and $\mathcal H_2$, a size Ramsey game is played on the edge set of $K_\mathbb{N}$. In every round, Builder selects an edge and Painter colours it red or blue. Builder is trying to force Painter to create a red copy of a graph from $\mathcal H_1$ or a blue copy of a graph from $\mathcal H_2$ as soon as possible. The online (size) Ramsey number $\tilde{r}(\mathcal H_1,\mathcal H_2)$ is the smallest number of rounds in the game provided Builder and Painter play optimally. We prove that if $\mathcal H_1$ is the family of all odd cycles and $\mathcal H_2$ is the family of all connected graphs on $n$ vertices and $m$ edges, then $\tilde{r}(\mathcal H_1,\mathcal H_2)\ge \varphi n + m-2\varphi+1$, where $\varphi$ is the golden ratio, and for $n\ge 3$, $m\le (n-1)^2/4$ we have $\tilde{r}(\mathcal H_1,\mathcal H_2)\le n+2m+O(\sqrt{m-n+1})$. We also show that $\tilde{r}(C_3,P_n)\le 3n-4$ for $n\ge 3$. As a consequence we get $2.6n-3\le \tilde{r}(C_3,P_n)\le 3n-4$ for every $n\ge 3$.

Détail

DOI : 10.37236/11644

Classification : 05C57, 91A43, 91A46, 05C75, 05C55, 05D10
Mots-clés : Ramsey game