On an anti-Ramsey threshold for random graphs

Autor(es)

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

Afiliação do(s) autor(es)

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

• Tipo de documento: Artigo Científico
• Fonte: EUROPEAN JOURNAL OF COMBINATORICS; v. 40, p. 26-41, AUG 2014.
• Citações Web of Science: 2

Resumo

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)

• Processo FAPESP: 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação
• Beneficiário: Carlos Eduardo Ferreira
• Linha de fomento: Auxílio à Pesquisa - Temático
• Processo FAPESP: 13/07699-0 - Centro de Pesquisa, Inovação e Difusão em Neuromatemática - NeuroMat
• Beneficiário: Jefferson Antonio Galves
• Linha de fomento: Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs
• Processo FAPESP: 12/00036-2 - Combinatória assintótica de estruturas esparsas e regularidade
• Beneficiário: Guilherme Oliveira Mota
• Linha de fomento: Bolsas no Exterior - Estágio de Pesquisa - Doutorado
• Processo FAPESP: 09/06294-0 - Combinatória assintótica de estruturas esparsas e regularidade
• Beneficiário: Guilherme Oliveira Mota
• Linha de fomento: Bolsas no Brasil - Doutorado