Ordered Ramsey exponent gap for matchings

Open problem: true ordered Ramsey number of matchings · arXiv:1410.5292

arXiv Informal low confidence— first stated 2016-04-25

Authors: David Conlon, Jacob Fox, Choongbum Lee, Benny Sudakov

Status open high confidence

The gap between the lower bound $r_<(M) \geq n^{c\log n/\log\log n}$ and the upper bound $r_<(M) \leq n^{\lceil\log n\rceil}$ for the ordered Ramsey number of an ordered matching on $n$ vertices remains open as of 2025. A 2025 survey by Balko explicitly lists this as Problem 1 in the field. Partial progress has been made for restricted classes of matchings (non-crossing matchings and matchings with interval chromatic number 2), but the main diagonal question is unresolved.

Cited literature (2)

partial Off-diagonal ordered Ramsey numbers of matchings (2018)

Dhruv Rohatgi · arXiv preprint · arXiv:1808.04025

Proves near-linear bounds for non-crossing ordered matchings and a sub-quadratic upper bound for random matchings with interval chromatic number 2, but does not resolve the main diagonal gap between n^{c log n/log log n} and n^{log n}.
survey A Survey on Ordered Ramsey Numbers (2025)

Martin Balko · arXiv preprint · arXiv:2502.02155

Explicitly lists the gap between the lower and upper bounds for ordered Ramsey numbers of matchings as Problem 1, confirming the conjecture remains open; also records an improved lower bound of \Omega((n/\log n)^2) for matchings with interval chromatic number 2 by Balko-Jelínek-Valtr.

Reviewer notes. The 2025 survey by Balko (arXiv:2502.02155) is the most comprehensive recent reference; it confirms the main diagonal gap is still open and records it as Problem 1. For the off-diagonal variant (matchings vs triangles), bounds have improved but that is a different question from the one posed here.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Informal. What is the true ordered Ramsey number of an ordered matching $M$ on $n$ vertices? Theorem 1.1 gives the lower bound $r_<(M) \geq n^{c\log n/\log\log n}$ for some labeling, while Theorem 1.2 gives $r_<(M) \leq n^{\lceil \log n \rceil}$; the authors describe the upper bound as 'almost matching' but the gap remains open.

Context

For ordinary matchings the Ramsey number is clearly linear, but for ordered matchings the paper shows the ordered Ramsey number can be superpolynomial. The precise exponent (between $c\log n/\log\log n$ and $\log n$) is not determined.

Notes. PDF source — math may be garbled; no explicit Problem/Question environment; inferred from the 'almost matching' description of the two bounds. Sections 5–6 containing the explicit open-problem list are not present in the provided text.

Source paper

Ordered Ramsey numbers
David Conlon, Jacob Fox, Choongbum Lee, Benny Sudakov · 2016-04-25
https://arxiv.org/abs/1410.5292 PDF source