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 sparse graphs with one triangle

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, Rua Matao 1010, BR-05508090 Sao Paulo - Brazil
Número total de Afiliações: 1
Tipo de documento: Artigo Científico
Fonte: JOURNAL OF GRAPH THEORY; v. 87, n. 2, p. 176-187, FEB 2018.
Citações Web of Science: 1
Resumo

For graphs G and H, let G -> (rb)(p) H denote the property that for every proper edge-coloring of G (with an arbitrary number of colors) there is a rainbow copy of H in G, that is, a copy of H with no two edges of the same color. The authors (2014) proved that, for every graph H, the threshold function P-H(rb) = P-H(rb)(n) of this property for the binomial random graph G (n, p) is asymptotically at most n(-1/m(2)(H)), where m((2))(H) denotes the so-called maximum 2-density of H. Nenadov et al. (2014) proved that if H is a cycle with at least seven vertices or a complete graph with at least 19 vertices, then P-H(rb) = n(-1/m(2)(H)). We show that there exists a fairly rich, infinite family of graphs.. containing a triangle such that if p >= Dn(-beta) for suitable constants D = D(F) > 0 and beta = beta(F), where beta > 1/m((2))(F), then G (n, p) -> (rb)(p) F almost surely. In particular, p(F)(rb) << n(-1/m(2)(F)) for any such graph F. (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/11431-2 - Combinatória extremal e probabilística
Beneficiário:Guilherme Oliveira Mota
Linha de fomento: Bolsas no Brasil - Pós-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
Processo FAPESP: 13/20733-2 - Combinatória extremal e probabilística
Beneficiário:Guilherme Oliveira Mota
Linha de fomento: Bolsas no Exterior - Estágio de Pesquisa - Pós-Doutorado