Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

On an anti-Ramsey threshold for random graphs

Texto completo
Autor(es):
Kohayakawa, Y. [1] ; Konstadinidis, P. B. [1] ; Mota, G. O. [1]
Número total de Autores: 3
Afiliação do(s) autor(es):
[1] Univ Sao Paulo, Inst Matemat & Estat, BR-05508090 Sao Paulo - Brazil
Número total de Afiliações: 1
Tipo de documento: Artigo Científico
Fonte: EUROPEAN JOURNAL OF COMBINATORICS; v. 40, p. 26-41, AUG 2014.
Citações Web of Science: 3
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: 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: 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: 09/06294-0 - Combinatória assintótica de estruturas esparsas e regularidade
Beneficiário:Guilherme Oliveira Mota
Linha de fomento: Bolsas no Brasil - Doutorado