The anti-Ramsey threshold of complete graphs

Autor(es)

Kohayakawa, Yoshiharu ; Mota, Guilherme Oliveira ; Parczyk, Olaf ; Schnitzer, Jakob

• Tipo de documento: Artigo Científico
• Fonte: DISCRETE MATHEMATICS; v. 346, n. 5, p. 12-pg., 2023-02-01.

Resumo

For graphs G and H, let G rb--> H denote the property that, for every proper edge-colouring of G, there is a rainbow H in G. For every graph H, the threshold function prbH = prbH(n) of this property in the random graph G(n, p) satisfies pHrb = O (n-1/m(2)(H)), where m(2)(H) denotes the so-called maximum 2-density of H. Completing a result of Nenadov, Person, Skoric acute accent , and Steger [J. Combin. Theory Ser. B 124 (2017), 1-38], we prove a matching lower bound for pKrbk for k 5. Furthermore, we show that pKrb4 =n-7/15 n-1/m(2)(K4). (c) 2023 Elsevier B.V. All rights reserved. (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: 19/13364-7 - Problemas extremais e estruturais em teoria dos grafos
• Beneficiário: Cristina Gomes Fernandes
• Modalidade de apoio: Auxílio à Pesquisa - Regular