Online Ramsey numbers of ordered paths and cycles

Felix Christian Clemen; Emily Heath; Mikhail Lavrov

paper

Online Ramsey numbers of ordered paths and cycles

arXiv:2210.05235

Abstract

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 lo g_{2} 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 $P_{n}$ by adding one edge.