Supersaturation of C4: From Zarankiewicz towards Erdos-Simonovits-Sidorenko

For a positive integer n, a graph F and a bipartite graph G subset of K-n,K-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 subset of K-n,K-n with m edges. The study of such a function is the subject of theorems of supersaturated graphs and closely related to the Sidorenko-Erdos-Simonovits conjecture as well. In the present paper we investigate the case when F = K-2.t and in particular the quadrilateral graph case. For F = C-4, 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 = K-2.t if m and the corresponding Zarankiewicz number differ by c . n root n 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. (C) 2018 Elsevier Ltd. All rights reserved.