A General Upper Bound on Multicolor Ordered Ramsey Numbers

Martin Balko; Kl\'ara Grinerov\'a

En palabras de los autores

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.

Resultado principalEl resumen no menciona limitaciones.

A General Upper Bound on Multicolor Ordered Ramsey Numbers

En palabras de los autores

Más de Combinatoria y matemática discreta ese día

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