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)$.