On ordered Ramsey numbers of matchings versus triangles

Martin Balko¹ ; Marian Poljak²

¹Charles University in Prague
²Charles University

The electronic journal of combinatorics, Tome 31 (2024) no. 2

Résumé

For graphs $G^<$ and $H^<$ with linearly ordered vertex sets, the ordered Ramsey number $r_<(G^<,H^<)$ is the smallest positive integer $N$ such that any red-blue coloring of the edges of the complete ordered graph $K^<_N$ on $N$ vertices contains either a blue copy of $G^<$ or a red copy of $H^<$. Motivated by a problem of Conlon, Fox, Lee, and Sudakov (2017), we study the numbers $r_<(M^<,K^<_3)$ where $M^<$ is an ordered matching on $n$ vertices. We prove that almost all $n$-vertex ordered matchings $M^<$ with interval chromatic number 2 satisfy $r_<(M^<,K^<_3) \in \Omega((n/\log n)^{5/4})$ and $r_<(M^<,K^<_3) \in O(n^{7/4})$, improving a recent result by Rohatgi (2019). We also show that there are $n$-vertex ordered matchings $M^<$ with interval chromatic number at least 3 satisfying $r_<(M^<,K^<_3) \in \Omega((n/\log n)^{4/3})$, which asymptotically matches the best known lower bound on these off-diagonal ordered Ramsey numbers for general $n$-vertex ordered matchings.

Détail

DOI : 10.37236/12107

Classification : 05D10, 05C55
Mots-clés : \(n\)-vertex ordered matchings, interval chromatic number