ON K-4-FREE SUBGRAPHS OF RANDOM GRAPHS

For 0 < gamma less than or equal to 1 and graphs G and H, write G -->H -gamma any gamma-proportion of the edges of G spans at least one copy of H in G. As customary, write K-r for the complete graph on r vertice s. We show that for every fixed real eta > 0 there exists a constant C = C(eta) such that almost every random graph G(n,p) with p = p(n) gre ater than or equal to Cn(-2/5) satisfies G(n,p) -->K-2/3+eta(4). The p roof makes use of a variant of Szemeredi's regularity lemma for sparse graphs and is based on a certain superexponential estimate for tile n umber of pseudo-random tripartite graphs whose triangles are not too w ell distributed. Related results and a general conjecture concerning H -free subgraphs of random graphs in the spirit of the Erdos-Stone theo rem are discussed.