A note on restricted online Ramsey numbers of matchings

Vojtěch Dvořák¹

¹University of Cambridge

The electronic journal of combinatorics, Tome 28 (2021) no. 3

Résumé

Consider the following game between Builder and Painter. We take some families of graphs $\mathcal{G}_{1},\ldots,\mathcal{G}_t$ and an integer $n$ such that $n \geq R(\mathcal{G}_1,\ldots,\mathcal{G}_t)$. In each turn, Builder picks an edge of initially uncoloured $K_n$ and Painter colours that edge with some colour $i \in \left\{ 1,\ldots,t \right\}$ of her choice. The game ends when a graph $G_i$ in colour $i $ for some $G_i \in \mathcal{G}_i$ and some $i$ is created. The restricted online Ramsey number $\tilde{R}(\mathcal{G}_{1},\ldots,\mathcal{G}_t;n)$ is the minimum number of turns that Builder needs to guarantee the game to end. In a recent paper, Briggs and Cox studied the restricted online Ramsey numbers of matchings and determined a general upper bound for them. They proved that for $n=3r-1=R_2(r K_2)$ we have $\tilde{R}_{2}(r K_2;n) \leq n-1$ and asked whether this was tight. In this short note, we provide a general lower bound for these Ramsey numbers. As a corollary, we answer this question of Briggs and Cox, and confirm that for $n=3r-1$ we have $\tilde{R}_{2}(r K_2;n) = n-1$. We also show that for $n'=4r-2=R_3(r K_2)$ we have $\tilde{R}_{3}(r K_2;n') = 5r-4$.

Détail

DOI : 10.37236/10025

Classification : 05C57, 91A43, 91A05, 05D10, 05C70, 05C55
Mots-clés : lower bound for Ramsey numbers