Abstrakt
An online Ramsey game is a game between Builder and Painter, alternating in turns. They are given a fixed graph H and a an infinite set of independent vertices G.
In each round Builder draws a new edge in G 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) over tilde (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) over bar (H) defined as the minimum number such that there exists graph G with (r) over bar (H) edges where for any edge two-coloring G contains a monochromatic copy of H.
In this extended abstract, we introduce the concept of induced online Ramsey numbers: the induced online Ramsey number (r) over tilde (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 T-1, T-2,..., vertical bar T-i vertical bar = 1, such that (i ->infinity)lim (T-i)/(r) over bar (T-i) = 0.