Supersaturation of C4: From Zarankiewicz towards Erdős-Simonovits-Sidorenko

For a positive integer n, a graph F and a bipartite graph  G⊆Kn,n let F(n+n,G) denote the number of copies of F in G, and let F(n+n,m) denote the minimum number of copies of F in all graphs G⊆Kn,n with m edges. The study of such a function is the subject of theorems of supersaturated graphs and closely related to the Sidorenko-Erdős-Simonovits conjecture as well. In the present paper we investigate the case when F=K2,t and in particular the quadrilateral graph case. For F=C4, we obtain exact results if m and the corresponding Zarankiewicz number differ by at most n, by a finite geometric construction of almost difference sets. F=K2,t if m and the corresponding Zarankiewicz number differ by c⋅nn we prove asymptotically sharp results based on a finite field construction. We also study stability questions and point out the connections to covering and packing block designs.