Multicolor Ramsey numbers of ordered matchings
For an ordered graph $H$ and an integer $q \geq 2$, let $r_{ 0$ such that almost every perfect matching $M$ on $[n]$ satisfies $r_{ 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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.08157
curl -X POST /api/v1/records/arxiv/2609.08157/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.08157/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'