Balanced supersaturation and Turán numbers in random graphs

- Department of Mathematics, Miami University

- Department of Mathematics, Emory University

*Advances in Combinatorics*, July. https://doi.org/10.19086/aic.2024.3.

### Editorial introduction

Given a nonempty graph H and an integer n, denote by Fn(H) the collection of all graphs with vertex set {1,…,n} that are *H-free*, i.e., that do not contain H as a (not necessarily induced) subgraph. The study of the asymptotics of |Fn(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 |Fn(H)|≥2ex(n,H), where ex(n,H) denotes the largest number of edges of a graph from Fn(H). Conversely, Erdős, Frankl, and Rödl proved that |Fn(H)|≤2(1+o(1))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 |Fn(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 |Fn(H)|≤2O(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 |Fn(H)|, it suffices to establish the following “balanced supersaturation” property: Every n-vertex graph G with more than ex(n,H) edges necessarily contains a large collection 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 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 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).