Turan numbers of bipartite graphs plus an odd cycle

Author(s)

Allen, Peter ^[1] ; Keevash, Peter ^[2] ; Sudakov, Benny ^{[3, 4]} ; Verstraete, Jacques ^[5]

Affiliation

^[1] London Sch Econ, Dept Math, London - England

^[2] Univ Oxford, Inst Math, Oxford OX1 3LB - England

^[3] ETH, Dept Math, CH-8092 Zurich - Switzerland

^[4] Univ Calif Los Angeles, Dept Math, Los Angeles, CA 90095 - USA

^[5] Univ Calif San Diego, Dept Math, San Diego, CA 92103 - USA

• Document type: Journal article
• Source: JOURNAL OF COMBINATORIAL THEORY SERIES B; v. 106, p. 134-162, MAY 2014.
• Web of Science Citations: 9

Abstract

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 -> 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'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 >= 5, ex(n, F boolean OR [C-k]) similar to ex(n, F boolean OR C) 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 >= 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. (C) 2014 Elsevier Inc. All rights reserved. (AU)

• FAPESP's process: 10/09555-7 - Embedding, randomised and structural problems in extremal graph theory
• Grantee: Peter David Allen
• Support Opportunities: Scholarships in Brazil - Post-Doctoral