2022/01/13 by Araújo, Pedro, Martins, Taísa, Mattos, Letícia +3
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2201.05106
For graphs G and H, we write G \oversetrb\longrightarrow H if any proper edge-coloring of G contains 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) \oversetrb\longrightarrowH is at most n-1/m2(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/m2(H). In this paper, we devise a framework that provides a richer and more complex family of such graphs that includes all the previously known examples.