Supersaturation problem for color-critical graphs

详细信息    查看全文

• 作者：Oleg Pikhurko^a ; ¹ ; ^{O.Pikhurko@warwick.ac.uk} ; Zelealem B. Yilma^b ; ^{zyilma@qatar.cmu.edu}
• 关键词：Extremal graph theory ; Removal lemma ; Supersaturation ; Turá ; n function
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2017
• 出版时间：March 2017
• 年：2017
• 卷：123
• 期：Complete
• 页码：148-185
• 全文大小：725 K
• 卷排序：123

文摘

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.