On off-diagonal ordered Ramsey numbers of nested matchings

Abstract

For two graphs $G^{<}$ and $H^{<}$ with linearly ordered vertex sets, the ordered Ramsey number $r_{<}(G^{<},H^{<})$ is the minimum $N$ such that every red-blue coloring of the edges of the ordered complete graph on $N$ vertices contains a red copy of $G^{<}$ or a blue copy of $H^{<}$. For a positive integer $n$, a nested matching $N{M}_n^{<}$ is the ordered graph on $2n$ vertices with edges $\{i,2n-i+1\}$ for every $i=1,\dots ,n$. We improve bounds on the ordered Ramsey numbers $r_{<}(N{M}_n^{<},K_3^{<})$ obtained by Rohatgi, we disprove his conjecture by showing $4n+1\le r_{<}(N{M}_n^{<},K_3^{<})\le (3+\sqrt{5})n$ for every $n\ge 6$, and we determine the numbers $r_{<}(N{M}_n^{<},K_3^{<})$ exactly for $n=4,5$. As a corollary, this gives stronger lower bounds on the maximum chromatic number of $k$-queue graphs for every $k\ge 3$. We also prove $r_{<}(N{M}_m^{<},K_n^{<})=\Theta (mn)$ for arbitrary $m$ and $n$. We expand the classical notion of Ramsey goodness to the ordered case and we attempt to characterize all connected ordered graphs that are $n$-good for every $n\in \mathbb{N}$. In particular, we discover a new class of ordered trees that are $n$-good for every $n\in \mathbb{N}$, extending all the previously known examples.

17 pages, 7 figures, minor revisions