Ordered Ramsey numbers Original Research Article

Let D1,D2,…,Dk be simple digraphs with no directed cycles. The ordered Ramsey number ρ(D1,D2,…,Dk) is the least integer n such that every k-arc-colouring (C1,C2,…,Ck) of the transitive tournament TTn on n vertices contains a Ci-coloured Di for some i, 1⩽i⩽k. This definition is useful in stating several classical theorems in combinatorics in a unified way and looking at their possible generalizations. Let Sn, Sn′, Pn and tn, respectively, denote the out-star, in-star, directed path and an oriented tree on n vertices. In this paper, among other things we find ρ(tm,TTn),ρ(D,Pn2,Pn3,…,Pnk),ρ(Sm,Sn′), where D is any weakly connected acyclic digraph on n1 vertices.