Asymmetric Ramsey properties of random graphs involving cliques and cycles

Abstract

We say that G -> (F, H) if, in every edge coloring c : E(G) -> {1, 2}, we can find either a 1-colored copy of F or a 2-colored copy of H. The well-known states that the threshold for the property G(n, p) -> (F, H) is equal to n(-1/)m(2)((F,H)), where m(2)(F, H) is given by

m(2) (F, H) := max {e(J)/v(J) - 2 + 1/m(2)(H) : J subset of F, e(J) >= 1}.

for any pair of graphs F and H with m(2) (F) >= m(2)(H). In this article, we showthe 0-statement of theKohayakawaKreuter conjecture for every pair of cycles and cliques.