Supersaturation problem for color-critical graphs
Oleg Pikhurko, Zelealem B. Yilma · Journal of Combinatorial Theory Series B · 2016
The Turán function ex(n,F) of a graph F is the maximum number of edges in an F-free graph with n vertices. The classical results of Turán and Rademacher from 1941 led to the study of supersaturated graphs where the key question is to determine hF(n,q), the minimum number of copies of F that a graph with n vertices and ex(n,F)+q edges can have. We determine hF(n,q) asymptotically when F is color-critical (that is, F contains an edge whose deletion reduces its chromatic number) and q=o(n2). Determining the exact value of hF(n,q) seems rather difficult. For example, let c1 be the limit superior of q/n for which the extremal structures are obtained by adding some q edges to a maximum F-free graph. The problem of determining c1 for cliques was a well-known question of Erdős that was solved only decades later by Lovász and Simonovits. Here we prove that c1>0 for every color-critical F. Our approach also allows us to determine c1 for a number of graphs, including odd cycles, cliques with one edge removed, and complete bipartite graphs plus an edge.