Turan numbers of bipartite graphs plus an odd cycle

作者：Allen Peter^*; Keevash Peter; Sudakov Benny; Verstraete Jacques

来源：Journal of Combinatorial Theory - Series B, 2014, 106: 134-162.

DOI：10.1016/j.jctb.2014.01.007

• Turan numbers
• Cycles
• Regularity lemma

For an odd integer k, let C-k = {C-3, C-5, ... , C-k} denote the family of all odd cycles of length at most k and let C denote the family of all odd cycles. Erdos and Simonovits [10] conjectured that for every family F of bipartite graphs, there exists k such that ex(n, F boolean OR C-k) similar to ex(n, F boolean OR C) as n -%26gt; infinity. This conjecture was proved by Erdos and Simonovits when F = {C-4}, and for certain families of even cycles in [14]. In this paper, we give a general approach to the conjecture using Scott%26apos;s sparse regularity lemma. Our approach proves the conjecture for complete bipartite graphs K-2,K-l and K-3,K-3: we obtain more strongly that for any odd k %26gt;= 5, %26lt;br%26gt;ex(n, F boolean OR {C-k}) similar to ex(n, F boolean OR C) %26lt;br%26gt;and we show further that the extremal graphs can be made bipartite by deleting very few edges. In contrast, this formula does not extend to triangles - the case k = 3 - and we give an algebraic construction for odd t %26gt;= 3 of K-2,K-l-free C-3-free graphs with substantially more edges than an extremal K-2,K-l-free bipartite graph on n vertices. Our general approach to the Erdos-Simonovits conjecture is effective based on some reasonable assumptions on the maximum number of edges in an m by n bipartite F-free graph.

• 出版日期2014-5