On the Anti-Ramsey Threshold for Non-Balanced Graphs

Author(s)

Araujo, Pedro ; Martins, Taisa ; Mattos, Leticia ; Mendonca, Walner ; Moreira, Luiz ; Mota, Guilherme O.

• Document type: Journal article
• Source: ELECTRONIC JOURNAL OF COMBINATORICS; v. 31, n. 1, p. 21-pg., 2024-03-22.

Abstract

For graphs G, H, we write G(->)(rb) H if for every proper edge-coloring of G there is a rainbow copy of H, i.e., a copy where no color appears more than once. Kohayakawa, Konstadinidis and the last author proved that the threshold for G(n, p) (rb)(->) H is at most n(-1)/m(2)(H). Previous results have matched the lower bound for this anti-Ramsey threshold for cycles and complete graphs with at least 5 vertices. Kohayakawa, Konstadinidis and the last author also presented an infinite family of graphs H for which the anti-Ramsey threshold is asymptotically smaller than n(-1)/m(2). In this paper, we devise a framework that provides a richer family of such graphs. (AU)

• FAPESP's process: 18/04876-1 - Ramsey theory, structural graph theory and applications in Bioinformatics
• Grantee: Guilherme Oliveira Mota
• Support Opportunities: Research Grants - Young Investigators Grants
• FAPESP's process: 23/07695-6 - Monochromatic tilings and covers problems
• Grantee: Walner Mendonça dos Santos
• Support Opportunities: Scholarships in Brazil - Post-Doctoral
• FAPESP's process: 19/13364-7 - Extremal and structural problems in graph theory
• Grantee: Cristina Gomes Fernandes
• Support Opportunities: Regular Research Grants