Turán's Theorem for random graphs

Bobby DeMarco, Jeff Kahn

For a graph $G$, denote by $t_r(G)$ (resp. $b_r(G)$) the maximum size of a $K_r$-free (resp. $(r-1)$-partite) subgraph of $G$. Of course $t_r(G)\ge b_r(G)$ for any $G$, and Turán…