2016/12/29 by Alon, Noga, Kostochka, Alexandr, Shikhelman, Clara
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1612.09143
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')-1)/(v(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