Generalized Turán problems for even cycles

Abstract

© 2020 Elsevier Inc. Given a graph H and a set of graphs F, let ex(n,H,F) denote the maximum possible number of copies of H in an F-free graph on n vertices. We investigate the function ex(n,H,F), when H and members of F are cycles. Let Ck denote the cycle of length k and let Ck={C3,C4,…,Ck}. We highlight the main results below. (i) We show that ex(n,C2l,C2k)=Θ(nl) for any l,k≥2. Moreover, in some cases we determine it asymptotically: We show that [Figure presented] and that the maximum possible number of C6's in a C8-free bipartite graph is n3+O(n5/2). (ii) Erdős's Girth Conjecture states that for any positive integer k, there exist a constant c>0 depending only on k, and a family of graphs {Gn} such that |V(Gn)|=n, |E(Gn)|≥cn1+1/k with girth more than 2k. Solymosi and Wong [37] proved that if this conjecture holds, then for any l≥3 we have ex(n,C2l,C2l−1)=Θ(n2l/(l−1)). We prove that their result is sharp in the sense that forbidding any other even cycle decreases the number of C2l's significantly: For any k>l, we have ex(n,C2l,C2l−1∪{C2k})=Θ(n2). More generally, we show that for any k>l and m≥2 such that 2k≠ml, we have ex(n,Cml,C2l−1∪{C2k})=Θ(nm). (iii) We prove ex(n,C2l+1,C2l)=Θ(n2+1/l), provided a stronger version of Erdős's Girth Conjecture holds (which is known to be true when l=2,3,5). This result is also sharp in the sense that forbidding one more cycle decreases the number of C2l+1's significantly: More precisely, we have [Figure presented], and ex(n,C2l+1,C2l∪{C2k+1})=O(n2) for l>k≥2. (iv) We also study the maximum number of paths of given length in a Ck-free graph, and prove asymptotically sharp bounds in some cases