On a conjecture of Erdős and Simonovits: Even cycles.

Let F be a family of graphs. A graph is F-free if it contains no copy of a graph in F as a subgraph. A cornerstone of extremal graph theory is the study of the Turán number ex( n,F), the maximum number of edges in an F-free graph on n vertices. Define the Zarankiewicz number z( n,F) to be the maximum number of edges in an F-free bipartite graph on n vertices. Let C denote a cycle of length k, and let C denote the set of cycles C, where 3≤ℓ≤ k and ℓ and k have the same parity. Erdős and Simonovits conjectured that for any family F consisting of bipartite graphs there exists an odd integer k such that ex( n,F ∪ C) ∼ z( n,F) - here we write f(n) ∼ g(n) for functions f,g: ℕ → ℝ if lim f(n)/g(n)=1. They proved this when F ={ C} by showing that ex( n,{ C; C})∼z( n,C). In this paper, we extend this result by showing that if ℓ∈{2,3,5} and k>2ℓ is odd, then ex( n,C∪{ C}) ∼ z( n, C). Furthermore, if k>2ℓ+2 is odd, then for infinitely many n we show that the extremal C∪{ C}-free graphs are bipartite incidence graphs of generalized polygons. We observe that this exact result does not hold for any odd k<2ℓ, and furthermore the asymptotic result does not hold when ( ℓ,k) is (3, 3), (5, 3) or (5, 5). Our proofs make use of pseudorandomness properties of nearly extremal graphs that are of independent interest. [ABSTRACT FROM AUTHOR]