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 a lower bound conjectured by Fox, He and Wigderson for multicolor Ramsey numbers of acyclic digraphs. 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]$.

arXiv comment6 pages, no figures. Minor revisions to exposition, notation and references. Main results unchanged