For graphs $G$ and $H$, let $G {displaystylesmash{begin{subarray}{c} hbox{$tinyrm rb$} longrightarrow hbox{$tinyrm p$} end{subarray}}}H$ 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^{rm rb}_H=p^{rm rb}_H(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}koric, and Steger [J. Combin. Theory Ser. B 124 (2017),1-38] we prove a matching lower bound for $p^{rm rb}_{K_k}$ for $kgeq 5$. Furthermore, we show that $p^{rm rb}_{K_4} = n^{-7/15}$.
تحميل البحث