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
    0 references
    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
    0 references

    Identifiers