On an anti-Ramsey threshold for sparse graphs with one triangle

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, Rua Matao 1010, BR-05508090 Sao Paulo - Brazil

• 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: 09/06294-0 - Combinatória assintótica de estruturas esparsas e regularidade
• Beneficiário: Guilherme Oliveira Mota
• Modalidade de apoio: Bolsas no Brasil - Doutorado
• Processo FAPESP: 13/07699-0 - Centro de Pesquisa, Inovação e Difusão em Neuromatemática - NeuroMat
• Beneficiário: Oswaldo Baffa Filho
• Modalidade de apoio: Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs
• Processo FAPESP: 13/20733-2 - Combinatória extremal e probabilística
• Beneficiário: Guilherme Oliveira Mota
• Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Pós-Doutorado
• Processo FAPESP: 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação
• Beneficiário: Carlos Eduardo Ferreira
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 13/11431-2 - Combinatória extremal e probabilística
• Beneficiário: Guilherme Oliveira Mota
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado