Advances in anti-Ramsey theory for random graphs
Resumo
Dados grafos G e H, denotamos a seguinte propriedade por G ÝrÑpb H: para toda coloração própria das arestas de G (com uma quantidade arbitrária de cores) existe uma cópia multicolorida de H em G, i.e., uma cópia de H sem duas arestas da mesma cor. Sabe-se que, para todo grafo H, a função limiar prHb prHbpnq para essa propriedade no grafo aleatório binomial Gpn; pq é assintoticamente no máximo n 1{mp2qpHq, onde mp2qpHq denota a assim chamada 2-densidade máxima de H. Neste trabalho discutimos esse e alguns resultados recentes no estudo de propriedades anti-Ramsey para grafos aleatórios, e mostramos que se H C4 ou H K4 então prHb n 1{mp2qpHq, que está em contraste com os fatos conhecidos de que prCbk n 1{mp2qpCkq para Let r be a positive integer and let G and H be graphs. We denote by G Ñ pHqr the property that any colouring of the edges of G with at most r colours contains a monochromatic copy of H in G. In 1995, Ro¨dl and Rucin´ski determined the threshold for the property Gpn; pq Ñ pHqr for all graphs H. The maximum 2-density mp2qpHq of a graph H is denoted by mp2qpHq max ! ||VEppJJqq|| 12 : J H; |V pJ q| ¥ 3) ; where we suppose |V pHq| ¥ 3.
