Supersaturation Beyond Color-Critical Graphs

The supersaturation problem for a given graph F asks for the minimum number hF(n,q) of copies of F in an n-vertex graph with ex(n,F)+q edges. Subsequent works by Rademacher, Erdős, and Lovász and Simonovits determine the optimal range of q (which is linear in n) for cliques F such that hF(n,q) equals the minimum number tF(n,q) of copies of F obtained from a maximum F-free n-vertex graph by adding q new edges. A breakthrough result of Mubayi extends this line of research from cliques to color-critical graphs F, and this was further strengthened by Pikhurko and Yilma who established the equality hF(n,q)=tF(n,q) for 1≤q≤ϵFn and sufficiently large n. In this paper, we present several results on the supersaturation problem that extend beyond the existing framework. Firstly, we explicitly construct infinitely many graphs F with restricted properties for which hF(n,q)<q·tF(n,1) holds when n≫q≥4, thus refuting a conjecture of Mubayi. Secondly, we extend the result of Pikhurko–Yilma by showing the equality hF(n,q)=tF(n,q) in the range 1≤q≤ϵFn for any member F in a diverse and abundant graph family (which includes color-critical graphs, disjoint unions of cliques Kr, and the Petersen graph). Lastly, we prove the existence of a graph F for any positive integer s such that hF(n,q)=tF(n,q) holds when 1≤q≤ϵFn1-1/s, and hF(n,q)<tF(n,q) when n1-1/s/ϵF≤q≤ϵFn, indicating that q=Θ(n1-1/s) serves as the threshold for the equality hF(n,q)=tF(n,q). We also discuss some additional remarks and related open problems.