Supersaturation of $C_4$: from Zarankiewicz towards Erdős-Simonovits-Sidorenko

Abstract

For a positive integer $n$, a graph $F$ and a bipartite graph $G\subseteq K_{n,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\subseteq K_{n,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=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 differs by $Cn\sqrt{n}$ we prove asymptotically sharp results. We also study stability questions and point out the connections to covering and packing block designs.

References in corpus (2)

• On the logarithimic calculus and Sidorenko's conjecture
• Cycles of given lengths in hypergraphs