Generalized Turán problems for even cycles
Acta mathematica Universitatis Comenianae, Tome 88 (2019) no. 3, pp. 723-728
Dániel Gerbner; Ervin Győri; Abhishek Methuku; Máté Vizer; Dániel Gerbner; Ervin Győri; Abhishek Methuku; Máté Vizer. Generalized Turán problems for even cycles. Acta mathematica Universitatis Comenianae, Tome 88 (2019) no. 3, pp. 723-728. http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a56/
@article{AMUC_2019_88_3_a56,
     author = {D\'aniel Gerbner and Ervin Gy\H{o}ri and Abhishek Methuku and M\'at\'e Vizer and D\'aniel Gerbner and Ervin Gy\H{o}ri and Abhishek Methuku and M\'at\'e Vizer},
     title = { Generalized {Tur\'an} problems for even cycles},
     journal = {Acta mathematica Universitatis Comenianae},
     pages = {723--728},
     year = {2019},
     volume = {88},
     number = {3},
     url = {http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a56/}
}
TY  - JOUR
AU  - Dániel Gerbner
AU  - Ervin Győri
AU  - Abhishek Methuku
AU  - Máté Vizer
AU  - Dániel Gerbner
AU  - Ervin Győri
AU  - Abhishek Methuku
AU  - Máté Vizer
TI  - Generalized Turán problems for even cycles
JO  - Acta mathematica Universitatis Comenianae
PY  - 2019
SP  - 723
EP  - 728
VL  - 88
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a56/
ID  - AMUC_2019_88_3_a56
ER  - 
%0 Journal Article
%A Dániel Gerbner
%A Ervin Győri
%A Abhishek Methuku
%A Máté Vizer
%A Dániel Gerbner
%A Ervin Győri
%A Abhishek Methuku
%A Máté Vizer
%T Generalized Turán problems for even cycles
%J Acta mathematica Universitatis Comenianae
%D 2019
%P 723-728
%V 88
%N 3
%U http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a56/
%F AMUC_2019_88_3_a56

Voir la notice de l'article provenant de la source Comenius University

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.