Balanced supersaturation and Turán numbers in random graphs

Given a nonempty graph \(H\) and an integer \(n\), denote by \(\mathcal{F}_n(H)\) the collection of all graphs with vertex set \(\{1, \dotsc, n\}\) that are \(H\)-free, i.e., that do not contain \(H\) as a (not necessarily induced) subgraph. The study of the asymptotics of \(|\mathcal{F}_n(H)|\) has a long and rich history going back almost fifty years to the seminal work of Erdős, Kleitman, and Rothschild. Since every subgraph of an \(H\)-free graph is \(H\)-free, we have \(|\mathcal{F}_n(H)| \ge 2^{\mathrm{ex}(n,H)}\), where \(\mathrm{ex}(n,H)\) denotes the largest number of edges of a graph from \(\mathcal{F}_n(H)\). Conversely, Erdős, Frankl, and Rödl proved that \(|\mathcal{F}_n(H)| \le 2^{(1+o(1))\mathrm{ex}(n,H)}\) for every nonbipartite \(H\). While one can now find several different proofs of this result in the literature, the problem of bounding \(|\mathcal{F}_n(H)|\) from above remains open for all but a handful of special families of bipartite \(H\). A folklore conjecture attributed to Erdős states that \(|\mathcal{F}_n(H)| \le 2^{O(\mathrm{ex}(n,H))}\) for every \(H\) that contains a cycle.

One of the most significant contributions to this study is the work of Morris and Saxton, who realised that, in order to prove the conjectured upper bound on \(|\mathcal{F}_n(H)|\), it suffices to establish the following “balanced supersaturation” property: Every \(n\)-vertex graph \(G\) with more than \(\mathrm{ex}(n,H)\) edges necessarily contains a large collection \(\mathcal{H}\) of copies of \(H\) that are “well distributed” in the sense that no subset of edges of \(G\) is contained in too many graphs from \(\mathcal{H}\). Morris and Saxton conjectured that such balanced supersaturation property holds for every bipartite \(H\) and proved it in several important cases.

The authors show that the conjecture of Morris and Saxton holds under a mild assumption about the rate of growth of \(\mathrm{ex}(n,H)\) that is widely believed to hold for every bipartite \(H\) that has a cycle. Additionally, they prove that a stronger, explicit form of the Morris–Saxton conjecture holds whenever \(H\) has the (non-balanced) supersaturation property conjectured by Erdős and Simonovits and show that this stronger result implies optimal upper bounds for the largest number of edges in an \(H\)-free subgraph of the random graph \(G(n,p)\).