Metraipolis › archive › dc_b1de4ff15541
Multicolor Ramsey numbers of ordered matchings — arXiv:2609.08157
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.08157
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T14:48:55.942Z
- SHA-256 of the archived text
e9ed981c038cf2f1be49202f2f61478ffd8ebd2d030d97225a28abfa26230def- Stable URL of this page
https://metraipolis.com/documento/dc_b1de4ff15541
How to cite
Multicolor Ramsey numbers of ordered matchings — arXiv:2609.08157 — arXiv (en), https://arxiv.org/abs/2609.08157 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_b1de4ff15541 (Metraipolis archive dc_b1de4ff15541, sha256 e9ed981c038cf2f1be49202f2f61478ffd8ebd2d030d97225a28abfa26230def)
BibTeX
@misc{dcb1de4ff15541,
title = {Multicolor Ramsey numbers of ordered matchings — arXiv:2609.08157},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.08157},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_b1de4ff15541; sha256 e9ed981c038cf2f1be49202f2f61478ffd8ebd2d030d97225a28abfa26230def},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.08157. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
For an ordered graph $H$ and an integer $q \geq 2$, let $r_{<}(H;q)$ denote the $q$-color ordered Ramsey number of $H$. Conlon, Fox, Lee and Sudakov asked whether, for every $q \geq 3$, there is a constant $c_q$ such that $r_{<}(M;q) \leq n^{c_q\log n}$ for every ordered matching $M$ on $n$ vertices. We answer this negatively in a strong form: for every $q \geq 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]$.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-09 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.08157 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T14:32:29.844Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).