March 2017 April 2017 May 2017
Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa
123 4 1 12 3 4 5 6
5 678910 11 2 345678 7 8 9 10 11 12 13
12 1314 15 1617 18 9 1011121314 15 14 15 161718 19 20
19 20 21 22 23 24 25 16 1718192021 22 21 22 23 24 25 26 27
26 2728293031 23 2425262728 29 28 29 30 31
30

Many $T$ copies 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'\subset H, |V(H')|\geq 3}\left\{ \frac{e(H')-1}{v(H')-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 keep almost all copies of $K_m$ in an $H$-free subgraph of $G(n,p)$, 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)$, 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$. The reason for this is that although $K_m$ has the minimum average degree among the $m$-color-critical graphs, it does not have the smallest $m_2(G)$ among such graphs. This is joint work with N. Alon and C. Shikhelman.