Ordered and canonical Ramsey numbers of stars (Q1359377)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Ordered and canonical Ramsey numbers of stars |
scientific article |
Statements
Ordered and canonical Ramsey numbers of stars (English)
0 references
4 November 1997
0 references
A canonical version of Ramsey's theorem proved by Erdös and Rado, implies that given any acyclic digraph \(D\), there exits a least integer \(\rho_c (D)=n\), such that every arc colouring (with an arbitrary number of colours) of the transitive tournament \(TT_n\) contains a canonically coloured \(D\) (in the sense of Erdös-Rado). It follows that if \(P_m\) is a directed path and \(D\) is an acyclic digraph, then there exits a least integer \(\rho_* (P_m,D) =n\) such that every arc colouring of \(TT_n\), with an arbitrary number of colours, contains either a \(P_m\) with no two arcs of the same colour, or a monochromatic \(D\). Recently, other authors have studied \(\rho_* (P_m,P_n)\) and \(\rho_* (P_m,T_n)\). In this paper \(\rho_* (P_m,S_n)\) is found, where \(S_n\) is the out-star, and bounds are given for \(\rho_c (S_{m,n})\), where \(S_{m,n}\) is the directed star with \(m\) in-arcs and \(n\) out-arcs at the centre.
0 references
canonical Ramsey numbers
0 references
Ramsey's theorem
0 references
digraph
0 references
transitive tournament
0 references
bounds
0 references
directed star
0 references