Supersaturation problem for color-critical graphs - Oleg Pikhurko (23277277) (2017)
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 h F ( 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 h F ( 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 h F ( n , q ) seems rather difficult. For example, let c 1 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 c 1 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 c 1 > 0 for every color-critical F. Our approach also allows us to determine c 1 for a number of graphs, including odd cycles, cliques with one edge removed, and complete bipartite graphs plus an edge. Other Information Published in: Journal of Combinatorial Theory, Series B License: http://creativecommons.org/licenses/by/4.0/ See article on publisher's website: https://dx.doi.org/10.1016/j.jctb.2016.12.001