Abstract:

Let H be a graph with chi(H) = r+1. Simonovits's theorem states that, if H is edge-critical, the unique largest H-free subgraph of K_n is its largest r-partite subgraph, provided that n is sufficiently large. We show that the same holds with K_n replaced by the binomial random graph G_{n,p} whenever H is also strictly 2-balanced and p >= (theta_H+o(1)) n^(-1/m_2(H)) (log n)^(1/(e_H-1)) for some explicit constant theta_H, which we believe to be optimal. This (partially) resolves a conjecture of DeMarco and Kahn.
This is joint work with Ilay Hoshen (TAU).