Ordered Ramsey number matching vs triangle magnitude

Status partial high confidence

The conjecture asks for the correct order of magnitude of $r_<(M, K_3)$ for an ordered matching $M$ on $n$ vertices, with the original gap between a lower bound of $\Omega((n/\log n)^{4/3})$ and the trivial upper bound $O(n^2/\log n)$. Balko and Poljak (2024) made significant partial progress: for almost all $n$-vertex ordered matchings with interval chromatic number 2, they establish $r_<(M^<, K^<_3) \in \Omega((n/\log n)^{4/3}) \cap O(n^{7/4})$, improving the upper-bound exponent from 2 to 7/4 for this class. The correct order of magnitude for general ordered matchings remains open.

Cited literature (1)

• partial On ordered Ramsey numbers of matchings versus triangles (2024)
  Balko, Martin; Poljak, Marian · Electronic Journal of Combinatorics · arXiv:2305.17933

  For almost all $n$-vertex ordered matchings with interval chromatic number 2, proves $r_<(M^<,K^<_3) \in \Omega((n/\log n)^{4/3}) \cap O(n^{7/4})$, narrowing the exponent gap from $[4/3, 2]$ to $[4/3, 7/4]$ for this class; also shows matchings with interval chromatic number $\geq 3$ attain the general lower bound $\Omega((n/\log n)^{4/3})$; the full question for all ordered matchings remains open.

Reviewer notes. Balko and Poljak (arXiv:2305.17933, published in Electronic Journal of Combinatorics 2024, vol. 31(2), P2.23) is the main follow-up directly addressing this problem. An extended abstract appeared at EuroComb 2023. The paper cites an earlier partial result by Rohatgi (2019) as prior art. The correct order of magnitude for all ordered matchings — not just those with bounded interval chromatic number — remains open.

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