Many cliques in H-free subgraphs of random graphs

For two fixed graphs T and H let ex(G(n,p),T,H) be the random variable counting the maximum number of copies of T in an H-free subgraph of the random graph G(n,p). We show that for the case T=Km and χ(H)>m the behavior of ex(G(n,p),Km,H) depends strongly on the relation between p and m2(H)=maxH′⊆H,|V(H′)|′≥3{e(H′)−1v(H′)−2}. When m2(H)>m2(Km) we prove that with high probability, depending on the value of p, either one can maintain almost all copies of Km, or it is asymptotically best to take a χ(H)−1 partite subgraph of G(n,p). The transition between these two behaviors occurs at p=n−1/m2(H). When m2(H)<m2(Km) we show that the above cases still exist, however for δ>0 small at p=n−1/m2(H)+δ one can typically still keep most of the copies of Km in an H-free subgraph of G(n,p). Thus, the transition between the two behaviors in this case occurs at some p significantly bigger than n−1/m2(H). To show that the second case is not redundant we present a construction which may be of independent interest. For each k≥4 we construct a family of k-chromatic graphs G(k,ϵi) where m2(G(k,ϵi)) tends to (k+1)(k−2)2(k−1)<m2(Kk−1) as i tends to infinity. This is tight for all values of k as for any k-chromatic graph G, m2(G)>(k+1)(k−2)2(k−1).