On an anti-Ramsey threshold for random graphs

• DOI: 10.1016/j.ejc.2014.02.004
• Publication Date: 2014-03-04T11:45:26Z
• Authors: Y. Kohayakawa; P.B. Konstadinidis; G.O. Mota
• Keywords: 0101 mathematics; 01 natural sciences

Abstract 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).