On the Anti-Ramsey Threshold for Non-Balanced Graphs

Autor(es)

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

• Tipo de documento: Artigo Científico
• Fonte: ELECTRONIC JOURNAL OF COMBINATORICS; v. 31, n. 1, p. 21-pg., 2024-03-22.

Resumo

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)

• Processo FAPESP: 18/04876-1 - Teoria de Ramsey, teoria estrutural de grafos e aplicações em Bioinformática
• Beneficiário: Guilherme Oliveira Mota
• Modalidade de apoio: Auxílio à Pesquisa - Jovens Pesquisadores
• Processo FAPESP: 23/07695-6 - Problemas de particionamentos e coberturas monocromáticas
• Beneficiário: Walner Mendonça dos Santos
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• Processo FAPESP: 19/13364-7 - Problemas extremais e estruturais em teoria dos grafos
• Beneficiário: Cristina Gomes Fernandes
• Modalidade de apoio: Auxílio à Pesquisa - Regular