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 \log 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.
@article{10_37236_11610,
author = {Felix Christian Clemen and Emily Heath and Mikhail Lavrov},
title = {Online {Ramsey} numbers of ordered paths and cycles},
journal = {The electronic journal of combinatorics},
year = {2024},
volume = {31},
number = {4},
doi = {10.37236/11610},
zbl = {1556.05100},
url = {http://geodesic.mathdoc.fr/articles/10.37236/11610/}
}
TY - JOUR
AU - Felix Christian Clemen
AU - Emily Heath
AU - Mikhail Lavrov
TI - Online Ramsey numbers of ordered paths and cycles
JO - The electronic journal of combinatorics
PY - 2024
VL - 31
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/11610/
DO - 10.37236/11610
ID - 10_37236_11610
ER -
%0 Journal Article
%A Felix Christian Clemen
%A Emily Heath
%A Mikhail Lavrov
%T Online Ramsey numbers of ordered paths and cycles
%J The electronic journal of combinatorics
%D 2024
%V 31
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/11610/
%R 10.37236/11610
%F 10_37236_11610
Felix Christian Clemen; Emily Heath; Mikhail Lavrov. Online Ramsey numbers of ordered paths and cycles. The electronic journal of combinatorics, Tome 31 (2024) no. 4. doi: 10.37236/11610
