On off-diagonal ordered Ramsey numbers of nested matchings
share
For two graphs G^< and H^< with linearly ordered vertex sets, the ordered Ramsey number r_<(G^<,H^<) is the minimum N such that every red-blue coloring of the edges of the ordered complete graph on N vertices contains a red copy of G^< or a blue copy of H^<. For a positive integer n, a nested matching NM^<_n is the ordered graph on 2n vertices with edges {i,2n-i+1} for every i=1,…,n. We improve bounds on the ordered Ramsey numbers r_<(NM^<_n,K^<_3) obtained by Rohatgi, we disprove his conjecture by showing 4n+1 ≤ r_<(NM^<_n,K^<_3) ≤ (3+√(5))n for every n ≥ 6, and we determine the numbers r_<(NM^<_n,K^<_3) exactly for n=4,5. As a corollary, this gives stronger lower bounds on the maximum chromatic number of k-queue graphs for every k ≥ 3. We also prove r_<(NM^<_m,K^<_n)=Θ(mn) for arbitrary m and n. We expand the classical notion of Ramsey goodness to the ordered case and we attempt to characterize all connected ordered graphs that are n-good for every n∈ℕ. In particular, we discover a new class of ordered trees that are n-good for every n ∈ℕ, extending all the previously known examples.
READ FULL TEXT
