1Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, Hungary 2Karlsruhe Institute of Technology, Karlsruhe, Germany 3Universidad de Costa Rica, San José, Costa Rica
Acta mathematica Universitatis Comenianae, Tome 88 (2019) no. 3, pp. 773-778
Citer cet article
Ervin Győri; Nika Salia; Casey Tompkins; Oscar Zamora; Ervin Győri; Nika Salia; Casey Tompkins; Oscar Zamora. The maximum number of P_l copies in P_k-free graphs. Acta mathematica Universitatis Comenianae, Tome 88 (2019) no. 3, pp. 773-778. http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a64/
@article{AMUC_2019_88_3_a64,
author = {Ervin Gy\H{o}ri and Nika Salia and Casey Tompkins and Oscar Zamora and Ervin Gy\H{o}ri and Nika Salia and Casey Tompkins and Oscar Zamora},
title = { The maximum number of {P_l} copies in {P_k-free} graphs},
journal = {Acta mathematica Universitatis Comenianae},
pages = {773--778},
year = {2019},
volume = {88},
number = {3},
url = {http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a64/}
}
TY - JOUR
AU - Ervin Győri
AU - Nika Salia
AU - Casey Tompkins
AU - Oscar Zamora
AU - Ervin Győri
AU - Nika Salia
AU - Casey Tompkins
AU - Oscar Zamora
TI - The maximum number of P_l copies in P_k-free graphs
JO - Acta mathematica Universitatis Comenianae
PY - 2019
SP - 773
EP - 778
VL - 88
IS - 3
UR - http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a64/
ID - AMUC_2019_88_3_a64
ER -
%0 Journal Article
%A Ervin Győri
%A Nika Salia
%A Casey Tompkins
%A Oscar Zamora
%A Ervin Győri
%A Nika Salia
%A Casey Tompkins
%A Oscar Zamora
%T The maximum number of P_l copies in P_k-free graphs
%J Acta mathematica Universitatis Comenianae
%D 2019
%P 773-778
%V 88
%N 3
%U http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a64/
%F AMUC_2019_88_3_a64
Generalizing Tur\'an's classical extremal problem, Alon and Shikhelman investigated the problem of maximizing the number of copies of $T$ in an $H$-free graph, for a pair of graphs $T$ and $H$. Whereas Alon and Shikhelman were primarily interested in determining the order of magnitude for some classes of graphs $H$, we focus on the case when $T$ and $H$ are paths, where we find asymptotic and exact results in some cases. We also consider other structures like stars and the set of cycles of length at least $k$, where we derive asymptotically sharp estimates. Our results generalize well-known extremal theorems of Erd\H{o}s and Gallai.
