On an anti-Ramsey threshold for random graphs

For graphs G and H , let G ⟶ p rb H denote the property that, for every proper edge-colouring of G (with an arbitrary number of colours) there is a totally multicoloured, or rainbow, copy of H in G , that is, a copy of H with no two edges of the same colour. We consider the problem of establishing the threshold p H rb = p H rb ( n ) of this property for the binomial random graph G ( n , p ) . More specifically, we give an upper bound for p H rb and we extend our result to certain locally bounded colourings that generalize proper colourings. Our method is heavily based on a characterization of sparse quasi-randomness given by Chung and Graham (2008).