Generalized Turán problems for even cycles

Gerbner, Dániel and Győri, Ervin and Methuku, Abhishek and Vizer, Máté (2019) Generalized Turán problems for even cycles. ACTA MATHEMATICA UNIVERSITATIS COMENIANAE, 88 (3). pp. 723-728. ISSN 0862-9544

Preview

Text 1712.07079.pdf Download (386kB) | Preview

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 $Ck$ denote the cycle of length $k$ and let $\mathscr{C}k= C3,C4,łdots,Ck $. We highlight the main results below. (i) We show that $ex(n, C{2l}, C{2k}) = Θ(nl)$ 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 $ Gn $ such that $|V(Gn)|=n$, $|E(Gn)|\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})=Θ(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})=Θ(n{2+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 $C{2l+1}$'s significantly.

Actions (login required)

Edit Item