Multicolor Ramsey numbers of ordered matchings

@misc{li2026multicolor,
  title = {{Multicolor Ramsey numbers of ordered matchings}},
  author = {Xiangyu Li},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.08157},
  eprint = {2609.08157},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.08157},
}

TY  - UNPB
TI  - Multicolor Ramsey numbers of ordered matchings
AU  - Xiangyu Li
PY  - 2026
DA  - 2026/09/08
PB  - arXiv
DO  - 10.48550/arxiv.2609.08157
UR  - https://arxiv.org/abs/2609.08157
AB  - For an ordered graph H and an integer q ≥ 2, let r_<(H;q) denote the q-color ordered Ramsey number of H. Conlon, Fox, Lee and Sudakov asked whether, for every q ≥ 3, there is a constant c_q such that r_<(M;q) ≤ n^c_qlog n for every ordered matching M on n vertices. We answer this negatively in a strong form: for every q ≥ 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/(loglog n)^q−1. This matches the general upper bound up to a factor of (loglog 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].
ER  -