Asymmetric Ramsey Properties of Random Graphs for Cliques and Cycles

Abstract

We say that $G\to (F,H)$ if, in every edge colouring $c:E(G)\to \{1,2\}$, we can find either a $1$-coloured copy of $F$ or a $2$-coloured copy of $H$. The well-known Kohayakawa--Kreuter conjecture states that the threshold for the property $G(n,p)\to (F,H)$ is equal to $n^{-1/m_2(F,H)}$, where $m_2(F,H)$ is given by \[ m_{2}(F,H):= \max \left\{\dfrac{e(J)}{v(J)-2+1/m_2(H)} : J \subseteq F, e(J)\ge 1 \right\}. \] In this paper, we show the $0$-statement of the Kohayakawa--Kreuter conjecture for every pair of cycles and cliques.

21 pages