On an anti-Ramsey threshold for random graphs

Author(s)

Kohayakawa, Y. ^[1] ; Konstadinidis, P. B. ^[1] ; Mota, G. O. ^[1]

Affiliation

^[1] Univ Sao Paulo, Inst Matemat & Estat, BR-05508090 Sao Paulo - Brazil

• Document type: Journal article
• Source: EUROPEAN JOURNAL OF COMBINATORICS; v. 40, p. 26-41, AUG 2014.
• Web of Science Citations: 2

Abstract

For graphs G and H, let G ->(rb)(p) 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). (C) 2014 Elsevier Ltd. All rights reserved. (AU)

• FAPESP's process: 13/03447-6 - Combinatorial structures, optimization, and algorithms in theoretical Computer Science
• Grantee: Carlos Eduardo Ferreira
• Support Opportunities: Research Projects - Thematic Grants
• FAPESP's process: 13/07699-0 - Research, Innovation and Dissemination Center for Neuromathematics - NeuroMat
• Grantee: Oswaldo Baffa Filho
• Support Opportunities: Research Grants - Research, Innovation and Dissemination Centers - RIDC
• FAPESP's process: 09/06294-0 - Asymptotic combinatorics of sparse structures and regularity
• Grantee: Guilherme Oliveira Mota
• Support Opportunities: Scholarships in Brazil - Doctorate
• FAPESP's process: 12/00036-2 - Asymptotic combinatorics of sparse structures and regularity
• Grantee: Guilherme Oliveira Mota
• Support Opportunities: Scholarships abroad - Research Internship - Doctorate