Upper bounds for ordered Ramsey numbers of forests and bounded-degree graphs

Abstract

We prove the following two upper bounds for ordered Ramsey numbers: (1) Every ordered forest $F$ on $n$ vertices satisfies $R_{<}(F,F)=O(n^{1+\lceil \log {\chi }_{<}(F)\rceil })$. This in particular answers a question of Geneson, Holmes, Liu, Neidinger, Pehova and Wass. (2) There is a function $f$ such that, for every fixed ordered graph $H$ with maximum degree at most $\Delta$ and interval chromatic number at most $k$, it holds that $R_{<}(H,K_n)=O_H(n^{f(\Delta ,k)})$.

arXiv comment11 pages, no figures. Comments welcome