The anti-Ramsey threshold of complete graphs

Author(s)

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

• Document type: Journal article
• Source: DISCRETE MATHEMATICS; v. 346, n. 5, p. 12-pg., 2023-02-01.

Abstract

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)

• 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: 19/13364-7 - Extremal and structural problems in graph theory
• Grantee: Cristina Gomes Fernandes
• Support Opportunities: Regular Research Grants