文摘
The Turán function ex(n,F)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)hF(n,q), the minimum number of copies of F that a graph with n vertices and ex(n,F)+qex(n,F)+q edges can have.We determine hF(n,q)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)q=o(n2).Determining the exact value of hF(n,q)hF(n,q) seems rather difficult. For example, let c1c1 be the limit superior of q/nq/n for which the extremal structures are obtained by adding some q edges to a maximum F -free graph. The problem of determining c1c1 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>0c1>0 for every color-critical F . Our approach also allows us to determine c1c1 for a number of graphs, including odd cycles, cliques with one edge removed, and complete bipartite graphs plus an edge.