Off-diagonal ordered Ramsey numbers of matchings (Q2415084)

Summary: For ordered graphs \(G\) and \(H\), the \textit{ordered Ramsey number} \(r_<(G,H)\) is the smallest $n$ such that every red/blue edge coloring of the complete ordered graph on vertices \(\{1,\ldots,n\}\) contains either a blue copy of \(G\) or a red copy of \(H\), where the embedding must preserve the relative order of vertices. One number of interest, first studied by \textit{D. Conlon} et al. [J. Comb. Theory, Ser. B 122, 353--383 (2017; Zbl 1350.05085)], is the \textit{off-diagonal} ordered Ramsey number \(r_<(M, K_3)\), where \(M\) is an ordered matching on \(n\) vertices. In particular, Conlon et al. asked what asymptotic bounds (in \(n\)) can be obtained for \(\max r_<(M, K_3)\), where the maximum is over all ordered matchings \(M\) on \(n\) vertices. The best-known upper bound is \(O(n^2/\log n)\), whereas the best-known lower bound is \(\Omega((n/\log n)^{4/3})\), and Conlon et al. [loc. cit.] hypothesize that there is some fixed \(\varepsilon > 0\) such that \(r_<(M, K_3) = O(n^{2-\varepsilon})\) for every ordered matching \(M\). We resolve two special cases of this conjecture. We show that the off-diagonal ordered Ramsey numbers for ordered matchings in which edges do not cross are nearly linear. We also prove a truly sub-quadratic upper bound for random ordered matchings with interval chromatic number $2$.