Turan numbers for bipartite graphs plus an odd cycle

Abstract

For an odd integer $k$, let ${\mathcal{C}}_k=\{C_3,C_5,...,C_k\}$ denote the family of all odd cycles of length at most $k$ and let $\mathcal{C}$ denote the family of all odd cycles. Erdős and Simonovits \cite{ESi1} conjectured that for every family $\mathcal{F}$ of bipartite graphs, there exists $k$ such that $\ex{n}{\mathcal{F} \cup \mathcal{C}_k} \sim \ex{n}{\mathcal{F} \cup \mathcal{C}}$ as $n\to \infty$. This conjecture was proved by Erdős and Simonovits when $\mathcal{F}=\{C_4\}$, and for certain families of even cycles in \cite{KSV}. 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,t}$ and $K_{3,3}$: we obtain more strongly that for any odd $k\ge 5$, \[ \ex{n}{\mathcal{F} \cup \{C_k\}} \sim \ex{n}{\mathcal{F} \cup \mathcal{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\ge 3$ of $K_{2,t}$-free $C_3$-free graphs with substantially more edges than an extremal $K_{2,t}$-free bipartite graph on $n$ vertices. Our general approach to the Erdős-Simonovits conjecture is effective based on some reasonable assumptions on the maximum number of edges in an $m$ by $n$ bipartite $\mathcal{F}$-free graph.