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: Binomial (polynomial); Ramsey Theory; Characterization

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