The anti-Ramsey threshold of complete graphs

被引：2

作者：

Kohayakawa, Yoshiharu ^{[1
]}

Mota, Guilherme Oliveira ^{[1
]}

Parczyk, Olaf ^{[2
]}

Schnitzer, Jakob ^{[3
]}

机构：

[1] Univ Sao Paulo, Inst Matemat & Estat, Sao Paulo, Brazil

[2] Free Univ Berlin, Fachbereich Math & Informat, Berlin, Germany

[3] Univ Hamburg, Fachbereich Math, Hamburg, Germany

来源：

DISCRETE MATHEMATICS | 2023年 / 346卷 / 05期

基金：

巴西圣保罗研究基金会;

关键词：

Anti-Ramsey property; Proper colourings; Random graphs; Thresholds;

D O I：

10.1016/j.disc.2023.113343

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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.

引用

页数：12

共 12 条

[1] Anti-Ramsey threshold of cycles?
Barros, Gabriel Ferreira
Cavalar, Bruno Pasqualotto
Mota, Guilherme Oliveira
Parczyk, Olaf
[J]. DISCRETE APPLIED MATHEMATICS, 2022, 323 : 228 - 235
[2] THRESHOLD FUNCTIONS
BOLLOBAS, B
THOMASON, A
[J]. COMBINATORICA, 1987, 7 (01) : 35 - 38
[3] THRESHOLD FUNCTIONS FOR SMALL SUBGRAPHS
BOLLOBAS, B
[J]. MATHEMATICAL PROCEEDINGS OF THE CAMBRIDGE PHILOSOPHICAL SOCIETY, 1981, 90 (SEP) : 197 - 206
[4] Bollobas Bela, 1998, GRAD TEXT M, V184, DOI 10.1007/978-1-4612-0619-4
[5] Conlon D, 2014, PROCEEDINGS OF THE INTERNATIONAL CONGRESS OF MATHEMATICIANS (ICM 2014), VOL IV, P303
[6] Janson S., 2000, WIL INT S D, DOI 10.1002/9781118032718
[7] On an anti-Ramsey threshold for sparse graphs with one triangle
Kohayakawa, Y.
Konstadinidis, P. B.
Mota, G. O.
[J]. JOURNAL OF GRAPH THEORY, 2018, 87 (02) : 176 - 187
[8] On an anti-Ramsey threshold for random graphs
Kohayakawa, Y.
Konstadinidis, P. B.
Mota, G. O.
[J]. EUROPEAN JOURNAL OF COMBINATORICS, 2014, 40 : 26 - 41
[9] An algorithmic framework for obtaining lower bounds for random Ramsey problems
Nenadov, Rajko
Person, Yury
Skoric, Nemanja
Steger, Angelika
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2017, 124 : 1 - 38
[10] THRESHOLD FUNCTIONS FOR RAMSEY PROPERTIES
RODL, V
RUCINSKI, A
[J]. JOURNAL OF THE AMERICAN MATHEMATICAL SOCIETY, 1995, 8 (04) : 917 - 942

← 1 2 →