Upper Bounds for Ordered Ramsey Numbers of Small 1-Orderings

Original · EN

A k-ordering of a graph G assigns distinct order-labels from the set {1,,|G|} to k vertices in G. Given a k-ordering H, the ordered Ramsey number R<(H) is the minimum n such that every edge-2-coloring of the complete graph on the vertex set {1,, n} contains a copy of H, the ith smallest vertex of which either has order-label i in H or no order-label in H. This paper conducts the first systematic study of ordered Ramsey numbers for 1-orderings of small graphs. We provide upper bounds for R<(H) for each connected 1-ordering H on 4 vertices. Additionally, for every 1-ordering H of the n-vertex path Pₙ, we prove that R<(H) ∈ O(n). Finally, we provide an upper bound for the generalized ordered Ramsey number R<(Kₙ, H) which can be applied to any k-ordering H containing some vertex with order-label 1.