Multicolor Ramsey numbers of ordered matchings

Abstract

For an ordered graph $H$ and an integer $q\ge 2$, let $r_{<}(H;q)$ denote the $q$-color ordered Ramsey number of $H$. Conlon, Fox, Lee and Sudakov asked whether, for every $q\ge 3$, there is a constant $c_q$ such that $r_{<}(M;q)\le n^{c_q\log n}$ for every ordered matching $M$ on $n$ vertices. We answer this negatively in a strong form: for every $q\ge 2$, there is $c_q>0$ such that almost every perfect matching $M$ on $[n]$ satisfies $r_{<}(M;q)>2^{c_q(\log n{)}^q/(\log \log n{)}^{q-1}}$. This matches the general upper bound up to a factor of $(\log \log n{)}^{q-1}$ in the exponent. We also give two applications. First, we prove the lower bound conjectured by Fox, He and Wigderson for multicolor Ramsey numbers of acyclic digraphs of bounded degree. Second, we strengthen a result of Axenovich, Rollin and Ueckerdt by giving a superquasipolynomial lower bound on the maximum chromatic number of $M$-free ordered graphs, for almost every perfect matching $M$ on $[n]$.

4 pages, no figures