Many $H$-copies in graphs with a forbidden tree

Abstract

For graphs $H$ and $F$, let $\mathrm{ex}(n,H,F)$ be the maximum possible number of copies of $H$ in an $F$-free graph on $n$ vertices. The study of this function, which generalises the well-studied Turán numbers of graphs, was initiated recently by Alon and Shikhelman. We show that if $F$ is a tree then $\mathrm{ex}(n,H,F)=\Theta (n^r)$ for some integer $r=r(H,F)$, thus answering one of their questions.

9 pages, 1 figure