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

Author(s)

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

Affiliation

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

• Document type: Journal article
• Source: JOURNAL OF GRAPH THEORY; v. 87, n. 2, p. 176-187, FEB 2018.
• Web of Science Citations: 1

Abstract

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)

• 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: 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: 13/20733-2 - Extremal and probabilistic combinatorics
• Grantee: Guilherme Oliveira Mota
• Support Opportunities: Scholarships abroad - Research Internship - Post-doctor
• 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/11431-2 - Extremal and probabilistic combinatorics
• Grantee: Guilherme Oliveira Mota
• Support Opportunities: Scholarships in Brazil - Post-Doctoral