Ordered Trees with Linear Off-Diagonal Ramsey Numbers

Source abstract

We characterize the following three classes of ordered trees: $\qquad$ (1) trees $T$ satisfying $R_<(T,K_n)=O(n)$; $\qquad$ (2) $χ$-bounding trees; $\qquad$ (3) Ramsey-good trees. In particular, we show that the first two classes coincide. The second characterization answers a question of Axenovich, Rollin and Ueckerdt, and the third resolves a problem of Balko and Poljak. In our proof, we also introduce several novel constructions of ordered graphs with sublinear independence number, giving lower bounds on $R_<(F,K_n)$ for various ordered forests $F$.