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

Nagy, Zoltán Lóránt (2019) Supersaturation of C4: From Zarankiewicz towards Erdős–Simonovits–Sidorenko. EUROPEAN JOURNAL OF COMBINATORICS, 75. pp. 19-31. ISSN 0195-6698

Preview

Text 1711.09282.pdf Download (230kB) | Preview

Abstract

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.

Actions (login required)

Edit Item