Balanced supersaturation and Turan numbers in random graphs

Tao Jiang, Sean Longbrake

Published 2022-08-22Version 1

In a ground-breaking work utilizing the container method, Morris and Saxton resolved a conjecture of Erd\H{o}s on the number of $C_{2\ell}$-free graphs on $n$ vertices and gave new bounds on the Turan number of $C_{2\ell}$ in the Erd\H{o}s-Renyi random graph $G(n,p)$. A key ingredient of their work is the so-called balanced supersaturation property of even cycles of a given length. This motivated Morris and Saxton to make a broad conjecture of the existence of such a property for all bipartite graphs. Roughly speaking, the conjecture states that given a bipartite graph $H$ if an $n$-vertex graph $G$ has its number of edges much larger than the Turan number $ex(n,H)$ then $G$ contains a collection of copies of $H$, in which no subset of edges of $G$ are covered more than some naturally expected number of times. In a subsequent breakthrough, Ferber, McKinley, and Samotij established a weaker version of the Morris-Saxton conjecture and applied it to derive far-reaching results on the enumeration problem of $H$-free graphs. However, this weaker version seems insufficient for applications to the Turan problem for random graphs. Building on these earlier works, in this paper, we essentially prove the conjecture of Morris and Saxton. We show that the conjecture holds when we impose a very mild assumption about $H$, which is widely believed to hold for all bipartite graphs. In addition to retrieving the enumeration results of Ferber, McKinley, and Samotij, we also obtain some general upper bounds on the Turan number $ex(G(n,p), H)$ of a bipartite graph $H$ in the random graph $G(n,p)$, from which Morris and Saxton's result on $ex(G(n,p), C_{2\ell})$ would also follow.