Supersaturation via edge-gluing

Abstract

In 1984, Erdős and Simonovits conjectured the following: given a bipartite graph $H$, there exist constants ${\hat{I}}^2,C>0$ such that any graph $G$ on $n$ vertices and $p{n}^2\ge C\mathrm{ex}(n,H)$ edges contains at least ${\hat{I}}^2{n}^{\mathrm{v}(H)}{p}^{\mathrm{e}(H)}$ copies of $H$. We show that edge-gluing preserves the satisfiability of this conjecture under some mild symmetry conditions. Namely, if two graphs $H_1$ and $H_2$ satisfy this conjecture, and if furthermore, gluing them along a fixed edge produces a unique graph then the resulting graph satisfies the conjecture as well. In the same paper, Erdős and Simonovits conjectured a weaker statement: for every $H$, there is some $\hat{I}\pm ,{\hat{I}}^2,C>0$ such that any graph $G$ on $n$ vertices and $p{n}^2\ge C{n}^{1+\hat{I}\pm }$ edges contains at least ${\hat{I}}^2{n}^{\mathrm{v}(H)}{p}^{\mathrm{e}(H)}$ copies of $H$. We show that if $H$ satisfies this conjecture then by gluing several copies of labeled $H$ along the same copy of a subforest of $H$ produces a graph that also satisfies the conjecture.

17 pages