Consider a two-player game between players Builder and Painter. Painter begins the game by picking a coloring of the edges of $K_n$, which is hidden from Builder. In each round, Builder points to an edge and Painter reveals its color. Builder's goal is to locate a particular monochromatic structure in Painter's coloring by revealing the color of as few edges as possible. The fewest number of turns required for Builder to win this game is known as the restricted online Ramsey number. In this paper, we consider the situation where this "particular monochromatic structure" is a large matching or a large tree. We show that in any $t$-coloring of $E(K_n)$, Builder can locate a monochromatic matching on at least $\frac{n-t+1}{t+1}$ edges by revealing at most $O(n\log t)$ edges. We show also that in any $3$-coloring of $E(K_n)$, Builder can locate a monochromatic tree on at least $n/2$ vertices by revealing at most $5n$ edges.
@article{10_37236_8649,
author = {Joseph Briggs and Christopher Cox},
title = {Restricted online {Ramsey} numbers of matchings and trees},
journal = {The electronic journal of combinatorics},
year = {2020},
volume = {27},
number = {3},
doi = {10.37236/8649},
zbl = {1441.05154},
url = {http://geodesic.mathdoc.fr/articles/10.37236/8649/}
}
TY - JOUR
AU - Joseph Briggs
AU - Christopher Cox
TI - Restricted online Ramsey numbers of matchings and trees
JO - The electronic journal of combinatorics
PY - 2020
VL - 27
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/8649/
DO - 10.37236/8649
ID - 10_37236_8649
ER -
%0 Journal Article
%A Joseph Briggs
%A Christopher Cox
%T Restricted online Ramsey numbers of matchings and trees
%J The electronic journal of combinatorics
%D 2020
%V 27
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/8649/
%R 10.37236/8649
%F 10_37236_8649
Joseph Briggs; Christopher Cox. Restricted online Ramsey numbers of matchings and trees. The electronic journal of combinatorics, Tome 27 (2020) no. 3. doi: 10.37236/8649
