Many cliques in $H$-free subgraphs of random graphs

Abstract

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=K_m$ and $\chi (H)>m$ the behavior of $ex(G(n,p),K_m,H)$ depends strongly on the relation between $p$ and $m_2(H)={\max }_{H^{\prime }\subset H,|V(H^{\prime }){|}^{\prime }\ge 3}\left\{\frac{e(H^{\prime })-1}{v(H^{\prime })-2}\right\}$. When $m_2(H)>m_2(K_m)$ we prove that with high probability, depending on the value of $p$, either one can maintain almost all copies of $K_m$, or it is asymptotically best to take a $\chi (H)-1$ partite subgraph of $G(n,p)$. The transition between these two behaviors occurs at $p=n^{-1/m_2(H)}$. When $m_2(H)<m_2(K_m)$ we show that the above cases still exist, however for $\delta >0$ small at $p=n^{-1/m_2(H)+\delta }$ one can typically still keep most of the copies of $K_m$ 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/m_2(H)}$. To show that the second case is not redundant we present a construction which may be of independent interest. For each $k\ge 4$ we construct a family of $k$ chromatic graphs $G(k,{\epsilon }_i)$ where $m_2(G(k,{\epsilon }_i))$ tends to $\frac{(k+1)(k-2)}{2(k-1)}(<m_2(K_{k-1}))$ as $i$ tends to infinity. This is tight for all values of $k$