Turán's Theorem for random graphs

Abstract

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's Theorem says that equality holds for complete graphs. With $G_{n,p}$ the usual ("binomial" or "Erdős-Rényi") random graph, we show: For each fixed r there is a C such that if \[ p=p(n) > Cn^{-\tfrac{2}{r+1}}\log^{\tfrac{2}{(r+1)(r-2)}}n, \] then $\mathrm{Pr}(t_r(G_{n,p})=b_r(G_{n,p}))\to 1$ as $n\to \infty$. This is best possible (apart from the value of $C$) and settles a question first considered by Babai, Simonovits and Spencer about 25 years ago.

69 pages