Online Ramsey Numbers of Ordered Paths and Cycles

An ordered graph is a graph with a linear ordering on its vertices. The online Ramsey game for ordered graphs G and H is played on an infinite sequence of vertices; on each turn, Builder draws an edge between two vertices, and Painter colors it red or blue. Builder tries to create a red G or a blue H as quickly as
possible, while Painter wants the opposite. The online ordered Ramsey number r$_o$(G, H) is the number of turns the game lasts with optimal play. In this paper, we consider the behavior of r$_o$(G, P$_n$) for fixed G, where P$_n$ is the monotone ordered path. We prove an O(n log2 n) bound on r$_o$(G, P$_n$) for all G and an O(n) bound when G is 3-ichromatic; we partially classify graphs G with r$_o$(G, P$_n$) = n + O(1). Many of these results extend to r$_o$(G, C$_n$), where C$_n$ is an ordered cycle obtained from Pn by adding one edge.