Generalized Turán problems for even cycles

Abstract

Given a graph $H$ and a set of graphs $\mathcal{F}$, let $ex(n,H,\mathcal{F})$ denote the maximum possible number of copies of $H$ in an $\mathcal{F}$-free graph on $n$ vertices. We investigate the function $ex(n,H,\mathcal{F})$, when $H$ and members of $\mathcal{F}$ are cycles. Let $C_k$ denote the cycle of length $k$ and let $\mathscr{C}_k=\{C_3,C_4,\ldots,C_k\}$. We highlight the main results below.
(i) We show that $ex(n, C_{2l}, C_{2k}) = \Theta(n^l)$ for any $l, k \ge 2$. Moreover, in some cases we determine it asymptotically. (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 $\{G_n\}$ such that $|V(G_n)|=n$, $|E(G_n)|\ge cn^{1+1/k}$ with girth more than $2k$.Solymosi and Wong proved that if this conjecture holds, then for any $l \ge 3$ we have $ex(n,C_{2l},\mathscr{C}_{2l-1})=\Theta(n^{2l/(l-1)})$. We prove that their result is sharp in the sense that forbidding any other even cycle decreases the number of $C_{2l}$'s significantly. (iii) We prove $ex(n,C_{2l+1},\mathscr{C}_{2l})=\Theta(n^{2+1/l}),$ provided a stronger version of Erd\H os'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 $C_{2l+1}$'s significantly.