Simonovits's theorem in random graphs

Abstract

Let be a graph with . Simonovits's theorem states that, if is edge‐critical, the unique largest ‐free subgraph of is its largest ‐partite subgraph, provided that is sufficiently large. We show that the same holds with replaced by the binomial random graph whenever is also strictly 2‐balanced and for some explicit constant , which we believe to be optimal. This (partially) resolves a conjecture of DeMarco and Kahn.