The maximum number of P_ℓ copies in P_k-free graphs

Generalizing Turán'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 Erdos and Gallai.