On ordered Ramsey numbers of matchings versus triangles

Abstract

For graphs $G^{<}$ and $H^{<}$ with linearly ordered vertex sets, the \ordered Ramsey number $r_{<}(G^{<},H^{<})$ is the smallest positive integer $N$ such that any red-blue coloring of the edges of the complete ordered graph $K_N^{<}$ on $N$ vertices contains either a blue copy of $G^{<}$ or a red copy of $H^{<}$. Motivated by a problem of Conlon, Fox, Lee, and Sudakov (2017), we study the numbers $r_{<}(M^{<},K_3^{<})$ where $M^{<}$ is an ordered matching on $n$ vertices. We prove that almost all $n$-vertex ordered matchings $M^{<}$ with interval chromatic number 2 satisfy $r_{<}(M^{<},K_3^{<})\in \Omega ((n/\log n{)}^{5/4})$ and $r_{<}(M^{<},K_3^{<})\in O(n^{7/4})$, improving a recent result by Rohatgi (2019). We also show that there are $n$-vertex ordered matchings $M^{<}$ with interval chromatic number at least 3 satisfying $r_{<}(M^{<},K_3^{<})\in \Omega ((n/\log n{)}^{4/3})$, which asymptotically matches the best known lower bound on these off-diagonal ordered Ramsey numbers for general $n$-vertex ordered matchings.

16 pages, 2 figures; extended abstract to appear at EuroComb 2023