A General Upper Bound on Multicolor Ordered Ramsey Numbers

Martin Balko; Kl\'ara Grinerov\'a

In the authors' words

We provide a general upper bound on multicolor ordered Ramsey numbers in terms of the interval chromatic number and the degeneracy of an ordered graph. We extend previous results by Conlon, Fox, Lee, and Sudakov (2017) by showing that for every $n$ -vertex ordered graph $G^{<}$ with degeneracy $d \geq 2$ , and interval chromatic number $χ$ , its $q$ -color ordered Ramsey number satisfies $r_{<} (G^{<}; q) \in n^{O (d^{q - 1} ⌈ l o g χ ⌉^{q - 1})}$ for every $q \geq 2$ . For fixed parameters $q, d, χ$ , the resulting estimate is polynomial in $n$ . For triangle-free ordered graphs $G^{<}$ , we also provide the stronger estimate $n^{O (q^{2} d ⌈ l o g χ ⌉^{q - 1})}$ . It also follows from a recent result by Li (2026) that our upper bound is almost tight for ordered matchings.

Main resultThe abstract does not state a limitation.

A General Upper Bound on Multicolor Ordered Ramsey Numbers

In the authors' words

More on Combinatorics & discrete math that day

Cubical Sheaf Complexes with Constant Expansion with Applications to Asymptotically Good qLTCs

A Szemer\'edi-Trotter Theorem in Arbitrary Fields

The Laplacian Sn,n​ conjecture is true

Smallest Cubic Non-1-Planar Graphs

Sparse Approximate Chromatic Profiles of Triangle-Free Graphs

The Laplacian $S_{n, n}$ conjecture is true