The anti-Ramsey threshold of complete graphs

Publication date: 1 February 2019

Abstract: For graphs

G

and

H

, let

iny m rb

l o n g r i g h t a r r o w h b o x

iny m p

denote the property that for every proper edge-colouring of

G

there is a rainbow

H

in

G

. It is known that, for every graph

H

, an asymptotic upper bound for the threshold function

p_{H}^{m r b} = p_{H}^{m r b} (n)

of this property for the random graph

G (n, p)

is

n^{- 1 / m^{(2)} (H)}

, where

m^{(2)} (H)

denotes the so-called maximum

2

-density of

H

. Extending a result of Nenadov, Person, v{S}kori'c, and Steger [J. Combin. Theory Ser. B 124 (2017),1-38] we prove a matching lower bound for

p_{K_{k}}^{m r b}

for

k g e q 5

. Furthermore, we show that

p_{K_{4}}^{m r b} = n^{- 7 / 15}

.

This page was built for publication: The anti-Ramsey threshold of complete graphs