Abstract

An online Ramsey game is a game between Builder and Painter, alternating in turns. They are given a graph H and a graph G of an infinite set of independent vertices. In each round Builder draws an edge and Painter colors it either red or blue. Builder wins if after some finite round there is a monochromatic copy of the graph H, otherwise Painter wins. The online Ramsey number r~(H) is the minimum number of rounds such that Builder can force a monochromatic copy of H in G. This is an analogy to the size-Ramsey number r(H) defined as the minimum number such that there exists graph G with r(H) edges where for any edge two-coloring G contains a monochromatic copy of H.

In this paper, we introduce the concept of induced online Ramsey numbers: the induced online Ramsey number r~ind(H) is the minimum number of rounds Builder can force an induced monochromatic copy of H in G. We prove asymptotically tight bounds on the induced online Ramsey numbers of paths, cycles and two families of trees. Moreover, we provide a result analogous to Conlon [On-line Ramsey Numbers, SIAM J. Discr. Math. 2009], showing that there is an infinite family of trees T1,T2,, |Ti|<|Ti+1| for i1, such that limir~(Ti)r(Ti)=0.