Helly Theorems for Generalized Turán Problems Sean English, Sam Spiro Abstract Given a graph T T and a family of graphs ℱ \mathcal{F} , the generalized Turán number ex ⁡ ( n , T , ℱ ) \mathrm{ex}(n,T,\mathcal{F}) is the maximum number of copies of T T in an n n -vertex ℱ \mathcal{F} -free graph. We prove a general theorem which states that for any tree T T , any family ℱ \mathcal{F} , and any integer k k , either ex ⁡ ( n , T , ℱ ) \mathrm{ex}(n,T,\mathcal{F}) is at least Ω ⁡ ( n k + 1 ) \Omega(n^{k+1}) or at most O ⁡ ( ex ​ ( n , ℱ ) k ) O(\mathrm{ex}(n,\mathcal{F})^{k}) , from which we derive a number of consequences. Our proofs rely on new variants of the classical Helly Theorem for trees which may be of independent interest. As far as we are aware, this is the first known application of Helly theorems for Turán type problems. 1 Introduction 1.1 Generalized Turán Problems One of the central areas of extremal combinatorics is the study of Turán numbers \mathrm{ex}(n,\mathcal{F}) for families of graphs \mathcal{F} , which is defined to be the maximum number of edges in an n -vertex \mathcal{F} -free graph. More generally, given a graph H and a family of graphs \mathcal{F} , we define the generalized Turán number \mathrm{ex}(n,H,\mathcal{F}) to be the maximum number of copies of H in an n -vertex \mathcal{F} -free graph. Note that \mathrm{ex}(n,K_{2},\mathcal{F})=\mathrm{ex}(n,\mathcal{F}) , so this is a generalization of the classical Turán number. The systematic study of generalized Turán numbers was initiated by Alon and Shikhelman [ 1 ] , and since then there has been a large number of results dedicated to the topic, see e.g. [ 14 , 16 , 17 , 22 , 25 ] . For a more thorough look at generalized Turán numbers we refer the interested reader to the excellent recent survey by Gerbner and Palmer [ 15 ] . In this paper we focus on generalized Turán numbers when H is a tree. Despite this being a natural extension of the H=K_{2} case of the classical Turán problem, there are surprisingly few results in this direction in the literature. Perhaps the first result of this form is the following which appeared in the original paper of Alon and Shikehlman. Theorem 1.1 ( [ 1 ] ) . If T,F are trees and if \mathrm{ex}(n,T,F)>0 for n sufficiently large, then \mathrm{ex}(n,T,F)=\Theta(n^{k}) for some integer k . While Theorem 1.1 is technically a result about generalized Turán numbers of trees, it also “misses the forest for the trees” in the sense that Letzter [ 21 ] showed that Theorem 1.1 continues to hold with T an arbitrary graph. Outside of Theorem 1.1 , the only other results which consider generalized Turán numbers for arbitrary trees T is a paper by Gerbner [ 13 ] who determined the order of magnitude of \mathrm{ex}(n,T,K_{2,t}) for all trees T , and an observation of Cambie, de Joannis de Verclos, and Kang [ 9 ] which determines the exact value of \mathrm{ex}(n,T,K_{1,t}) for all T . In terms of results for specific choices of trees T , the most substantial result we know of is a nice theorem of Füredi and Kündgen [ 11 ] which gives essentially optimal bounds on \mathrm{ex}(n,K_{1,t},\mathcal{F}) based on the classical Turán number \mathrm{ex}(n,\mathcal{F}) . A slightly weakened version of this result can be stated as follows. Theorem 1.2 ( [ 11 ] ) . Let \ell be an integer and \mathcal{F} a family of graphs which does not contain a subgraph of a star. If \mathrm{ex}(n,\mathcal{F})=\Theta(n^{2-\beta}) for some \beta<\ell^{-1} , then \mathrm{ex}(n,K_{1,\ell},\mathcal{F})=\Theta(\mathrm{ex}(n,\mathcal{F})^{\ell}n^{1-\ell}), and if \beta\geq\ell^{-1} then \mathrm{ex}(n,K_{1,\ell},\mathcal{F})=\Omega(n^{\ell}). The main result of this paper is a general bound on \mathrm{ex}(n,T,\mathcal{F}) for trees T which holds for any choice of T and any family \mathcal{F} , thereby greatly expanding on the limited set of previously known results listed above. Our result is spiritually similar to that of Theorem 1.2 in the sense that it either bounds \mathrm{ex}(n,T,\mathcal{F}) as a function of \mathrm{ex}(n,\mathcal{F}) or lower bounds it by some function independent of \mathrm{ex}(n,\mathcal{F}) . Specifically, our theorem implies that for any tree T , family \mathcal{F} , and integer k , either \mathrm{ex}(n,T,\mathcal{F})=\Omega(n^{k+1}) or \mathrm{ex}(n,T,\mathcal{F})=O(\mathrm{ex}(n,\mathcal{F})^{k}) . Our theorem moreover gives a criterion for determining whether the bound \Omega(n^{k+1}) or O(\mathrm{ex}(n,\mathcal{F})^{k}) holds for a given family \mathcal{F} , and to state this condition we need a technical definition. Definition 1 . Given a graph H , a set of vertices R\subseteq V(H) , and an integer q , we define the graph H_{R}^{q} to be the graph obtained by taking the union of q copies of H such that each of the copies agree on the set of vertices R and are otherwise disjoint. For each integer k\geq 1 we define \mathcal{F}_{H,k}^{q}:=\{H_{R}^{q}:R\subsetneq V(H),\ H-R\textrm{ has at least }k\textrm{ connected components}\}. See Figure 1 for an example of a graph of the form H_{R}^{q} . With this our main theorem can be stated as follows. (a) H=P_{6} . The vertices in R are red. (b) The graph H_{R}^{4} . Figure 1 : An example of the graph H_{R}^{4} from Definition 1 when H is the path on 6 vertices and R consists of the set of red vertices in Figure 1(a) . H_{R}^{4} is a member of the family \mathcal{F}_{H,3}^{4} since H-R has (at least) three connected components. Theorem 1.3 . Let T be a tree, \mathcal{F} a family of graphs, and k\geq 0 an integer. If there exists an integer q such that every \mathcal{F} -free graph is \mathcal{F}_{T,k+1}^{q} -free, then \mathrm{ex}(n,T,\mathcal{F})=O_{T,k,q}(\mathrm{ex}(n,\mathcal{F})^{k}), and if no such q exists then \mathrm{ex}(n,T,\mathcal{F})=\Omega_{T,k}(n^{k+1}). One can derive a number of powerful results using Theorem 1.3 together with some very short proofs. For example, one can prove the general statement that families \mathcal{F} with \mathrm{ex}(n,\mathcal{F}) small have \mathrm{ex}(n,T,\mathcal{F}) close to an integer whenever T is a tree. Theorem 1.4 . Let T be a tree and \mathcal{F} a family with \mathrm{ex}(n,\mathcal{F})=O(n^{1+\epsilon}) . If \mathrm{ex}(n,T,\mathcal{F})>0 for all sufficiently large n , then there exists an integer k such that \mathrm{ex}(n,T,\mathcal{F})=\Omega(n^{k}), and \mathrm{ex}(n,T,\mathcal{F})=O(n^{k+k\epsilon}). In particular, the case \epsilon=0 gives the following. Corollary 1.5 . For every tree T and family \mathcal{F} containing a forest, if \mathrm{ex}(n,T,\mathcal{F})>0 for all sufficiently large n , then there exists an integer k such that \mathrm{ex}(n,T,\mathcal{F})=\Theta(n^{k}) . This gives a two-way generalization of Theorem 1.1 , in the sense that we can forbid forests and not just trees, and we can also forbid an entire family of graphs rather than just a single graph. We emphasize that this result can be derived from the original method of Theorem 1.1 ; we highlight its particular statement here both to show the power of what can be proven using Theorem 1.3 , and also because the exact statement of Corollary 1.5 can be used to prove a sort of “stability” result for generalized Turán problems for trees. Corollary 1.6 . If T\neq K_{2} is a tree with \ell\geq 2 leaves and if \mathcal{F} is a family of graphs with \mathrm{ex}(n,T,\mathcal{F})=O(n^{\ell}) and \mathrm{ex}(n,T,\mathcal{F})>0 for all sufficiently large n , then \mathrm{ex}(n,T,\mathcal{F})=\Theta(n^{k}) for some integer k . In particular, if \mathrm{ex}(n,T,\mathcal{F})=o(n^{k}) for any integer k\leq\ell , then the generalized Turán number must in fact drop all the way down to O(n^{k-1}) . This sort of stability result is strongest when T has many leaves. It is well known that trees with few leaves have large diameter, and for such trees the following (more involved) consequence of Theorem 1.3 gives effective stability. Theorem 1.7 . Let k\geq 1 be an integer. If T is a tree of diameter d\geq 2k , then for every family of graphs \mathcal{F} with \mathrm{ex}(n,T,\mathcal{F})=o(n^{k+1}) , we have \mathrm{ex}(n,T,\mathcal{F})=O(n^{k+\frac{k(k-1)}{d-k}}). As we discuss below, this upper bound is tight for paths P_{d+1} with d\equiv 1\mod k-1 . Combining the argument used to prove Theorem 1.7 together with Corollary 1.6 allows us to show that all “small” generalized Turán numbers for trees must be very close to an integer power of n . Theorem 1.8 . For every tree T and 0<\epsilon\leq 1 , if \mathcal{F} is a family of graphs such that \mathrm{ex}(n,T,\mathcal{F})=O(n^{(\epsilon v(T))^{1/3}}), and such that \mathrm{ex}(n,T,\mathcal{F})>0 for all sufficiently large n ; then there exists some integer k such that \mathrm{ex}(n,T,\mathcal{F})=\Omega(n^{k}), and \mathrm{ex}(n,T,\mathcal{F})=O(n^{k+\epsilon}). This in turn yields the surprising fact that every non-integral exponents can be realized by only finitely many trees. Corollary 1.9 . For every non-integral number r\in\mathbb{R}_{\geq 0}\setminus\mathbb{Z} , there exists at most finitely many trees T with the property that there exists a family of graphs \mathcal{F} satisfying \mathrm{ex}(n,T,\mathcal{F})=\Theta(n^{r}) . One can use Theorem 1.3 to show that for every tree T there exists a (finite) family \mathcal{F} with \mathrm{ex}(n,T,\mathcal{F})=\Theta(n^{\ell}) where \ell is the number of leaves of T , and this implies that the assumption r\notin\mathbb{Z} is needed for Corollary 1.9 to hold. The applications above show the utility of our main result Theorem 1.3 . However, it is natural to ask whether these bounds are tight. In Appendix A we show that the upper bound of Theorem 1.3 (as well as that of Theorem 1.7 ) is tight whenever T=P_{t} is the path graph on t vertices and \mathcal{F}=\mathcal{F}_{P_{t},k+1}^{q} with q large provided t\equiv 2\mod k-1 . In particular, this shows that for every k there exist infinitely many trees for which the upper bound of Theorem 1.3 is best possible. At this point the reader might ask what happens for paths with t\not\equiv 2\mod k-1 . In this case it turns out we can refine Theorem 1.3 to give a further sharpening of the upper bound. Theorem 1.10 . Let \mathcal{F} be a family of graphs, and k,t\geq 3 integers with t\not\equiv 2\mod k-1 . If there exists an integer q such that every \mathcal{F} -free graph is \mathcal{F}_{P_{t},k+1}^{q} -free, then \mathrm{ex}(n,P_{t},\mathcal{F})=O_{t,k,q}(\mathrm{ex}(n,\mathcal{F})^{k-1}\cdot n), and if no such q exists then \mathrm{ex}(n,P_{t},\mathcal{F})=\Omega_{t,k}(n^{k+1}). That is, under the condition t\not\equiv 2\mod k-1 we can improve upon the upper bound of Theorem 1.3 by replacing one of the \mathrm{ex}(n,\mathcal{F}) terms with n . This result turns out to be tight whenever t\equiv 1\mod k-1 ; see Appendix A for details. In addition to being of interest in its own right, we believe Theorem 1.10 serves as a proof-of-concept that further refinements can be made for other trees. In particular, we comment on what might be true for arbitrary path lengths in the concluding remarks. 1.2 Helly Theorems One of our main tools for proving Theorem 1.3 and its refinement Theorem 1.10 are generalizations of the classical Helly theorem for trees which we believe are of independent interest. Historically, the first Helly-type theorems appeared in convex geometry when Helly [ 18 ] proved that if \mathcal{C} is a collection of convex sets in \mathbb{R}^{d} such that any subcollection \mathcal{C}^{\prime}\subseteq\mathcal{C} of size at least d+1 contains a point v^{\prime} in every element of \mathcal{C}^{\prime} , then there exists a point v which lies in every element of \mathcal{C} . There have since been many other Helly-type theorems which have been studied within convex geometry and beyond [ 3 , 4 , 5 , 6 , 19 ] . In order to recall the statement of the classical Helly Theorem for trees, as well as to state our new variant of this result, we introduce some definitions. Definition 2 . Given a tree T , a subtree system \mathcal{T} of T is a collection of subtrees of T . We say that a set of vertices U\subseteq V(T) pierces a subtree T^{\prime}\subseteq T if V(T^{\prime})\cap U\neq\emptyset , and we say that a set U pierces a subtree system \mathcal{T} if it pierces every T^{\prime}\in\mathcal{T} . Similarly, we say that a set of edges E\subseteq E(T) pierces a subtree T^{\prime}\subseteq T if a vertex in V(T^{\prime}) is incident with an edge in E , and we say E pierces a subtree system \mathcal{T} if it pierces every T^{\prime}\in\mathcal{T} . In this language, the classical Helly Theorem for trees states that if \mathcal{T} is a subtree system such that any pair of elements from \mathcal{T} is pierced by a single vertex, then there exists a vertex which pierces all of \mathcal{T} . Note that the case of T being a path essentially corresponds to the d=1 case of the classical Helly Theorem. To prove Theorem 1.3 , we will need a variant of the Helly Theorem for trees which guarantees a set of edges which pierces \mathcal{T} . Theorem 1.11 (Edge Helly Theorem) . Let T be a tree, \mathcal{T} a subtree system of T , and k\geq 0 an integer. If every subcollection \mathcal{T}^{\prime}\subseteq\mathcal{T} of size at most k+1 can be pierced by at most k edges, then \mathcal{T} can be pierced by at most k edges. As far as we are aware, our result Theorem 1.3 is the first known Turán result which is proven using Helly-type theorems. Moreover, one can show that our Edge Helly Theorem implies the classical Vertex Helly Theorem, and as such it is at least as strong as this classical result. In order to prove Theorem 1.10 for paths, one might expect that we need a Helly-type Theorem for paths which involves pirecing by a set of edges and a single vertex. While our argument implicitly uses ideas of this form, ultimately the proof requires us to use a more technical notion of piercing which we call “pseudo-piercing”. We defer the precise formulation of pseudo-piercing until Definition 5 due to it’s technical nature, but we emphasize here that we believe the notion of pseudo-piercing is novel and may provide avenues for future applications of Helly-type arguments to settings where such methods have not previously been used. 1.3 Organization, Notation, and Conventions The rest of the paper is organized as follows. In Section 2 , we show how to use Theorem 1.3 to prove Theorems 1.4 , 1.7 and 1.8 , along with Corollaries 1.5 , 1.6 and 1.9 . In Section 3 , we give some technical definitions and preliminary results, incuding the proof of Theorem 1.11 , which will all be necessary for proving our main theorem ( Theorem 1.3 ) and also Theorem 1.10 . In Section 4 , we prove Theorem 1.3 and also introduce the notion of pseudo-piercing. In Section 5 , we show how to refine Theorem 1.3 in the case of paths to prove Theorem 1.10 . Finally, in Section 6 , we provide some concluding remarks and open questions. We note that if \mathcal{F} contains an empty graph, then \mathrm{ex}(n,H,\mathcal{F}) is not defined for large n . As such we will silently assume through this work that every graph in \mathcal{F} contains at least one edge. Given a graph H we will write v(H):=|V(H)| and e(H):=|E(H)| . In our results and proofs involving a graph H which we count within another graph G , we will often add hats to vertices and sets associated to H in order to distinguish them from vertices and sets associated to G . For example, \hat{x} will refer to a vertex in H while x refers to one in G . For integers a,b,c\geq 1 , we define the generalized theta graph \theta_{a,b,c} to be the graph obtained by taking a paths on 1+cb vertices which all agree on the vertices 1,1+b,1+2b,\ldots,1+cb and which are otherwise pairwise disjoint. Equivalently, \theta_{a,b,c}=(P_{1+cb})_{R}^{a} where R=\{v_{1},v_{1+b},\ldots,v_{1+cb}\} . When c=1 the graph \theta_{a,b,c} is simply a so-called theta graph , and we write \theta_{a,b}:=\theta_{a,b,1} . 2 Applications In this section we establish the applications of Theorem 1.3 from the introduction in the order they were stated. Most of these applications have succinct proofs, with the one minor exception being the diameter result Theorem 1.7 . Proof of Theorem 1.4 . Let k\geq 0 be the largest integer such that \mathrm{ex}(n,T,\mathcal{F})=\Omega(n^{k}) . Because \mathrm{ex}(n,T,\mathcal{F})=\Omega(n^{k+1}) does not hold, by Theorem 1.3 we must have \mathrm{ex}(n,T,\mathcal{F})=O(\mathrm{ex}(n,\mathcal{F})^{k})=O(n^{k+k\epsilon}).\qed Corollary 1.5 follows immediately from Theorem 1.4 and the fact that \mathrm{ex}(n,\mathcal{F})=O(n) whenever \mathcal{F} contains a forest (see e.g. Theorem 2.32 in [ 12 ] ), so we omit a formal proof. Proof of Corollary 1.6 . If \mathcal{F} contains a forest then the result follows from Corollary 1.5 . Otherwise, consider the graph G obtained by duplicating each leaf of T a total of n/v(T) times. It is not difficult to see that G is a tree for T\neq K_{2} , and therefore is \mathcal{F} -free since the only subgraphs of G are forests. Moreover, G has at most n vertices and contains at least \Omega(n^{\ell}) copies of T , implying that \mathrm{ex}(n,T,\mathcal{F})=\Omega(n^{\ell}) . This combined with our hypothesis gives \mathrm{ex}(n,T,\mathcal{F})=\Theta(n^{\ell}) . ∎ Before we can prove Theorem 1.7 , we need a bound on the extremal number of the generalized theta graph \theta_{a,b,c} , which we will achieve by combining a classical result of Bondy and Simonvits [ 7 ] with a recent result of Dong, Gao, and Liu [ 10 ] . To state this latter result, we need a technical definition: given two graphs H_{1},H_{2} and vertices u_{1}\in V(H_{1}) and u_{2}\in V(H_{2}) , define H_{1}^{u_{1}}\odot H_{2}^{u_{2}} to be the graph obtained by taking the union of H_{1} and H_{2} and identifying u_{1} with u_{2} . Theorem 2.1 ( [ 10 ] ) . If H_{1},H_{2} are two copies of the same connected bipartite graph H and if u_{1}\in V(H_{1}) and u_{2}\in V(H_{2}) come from the same part of the bipartition, then \mathrm{ex}(n,H_{1}^{u_{1}}\odot H_{2}^{u_{2}})=\Theta(\mathrm{ex}(n,H)). Corollary 2.2 . We have \mathrm{ex}(n,\theta_{a,b,c})=O_{a,c}(n^{1+1/b}). Proof. We will prove this in the case when c is a power of 2. This will imply the result in general since for any c , if r is such that 2^{r-1}1+(k-1)b ), so T_{R}^{q}\in\mathcal{F}_{T,k+1}^{q} . Furthermore, it is straightforward to see that c_{2}(T_{R}^{q})=\theta_{q,b,k-1} . Putting this all together and applying Lemma 2.3 and Corollary 2.2 , we have \mathrm{ex}(n,\mathcal{F}_{T,k+1}^{q})\leq\mathrm{ex}(n,T_{R}^{q})=O(\mathrm{ex}(n,\theta_{q,b,k-1}))=O_{q}(n^{1+1/b})=O_{q}(n^{1+\frac{k-1}{d-k}}), (1) with this last inequality using b\geq\frac{(d-2)-(k-2)}{k-1}=\frac{d-k}{k-1} , proving the result. For the case k=1 , we aim to show \mathrm{ex}(n,\mathcal{F}_{T,2}^{q})=O_{q}(n) whenever T has diameter at least 2, i.e. whenever T\neq K_{1},K_{2} . Let R\subseteq V(T) denote the set of non-leaves of T . Since T\neq K_{1},K_{2} , the graph T-R consists of isolated vertices for each of the at least 2 leaves of T , so T_{R}^{q}\in\mathcal{F}_{T,2}^{q} . Moreover, T_{R}^{q} is simply the tree obtained by duplicating each leaf q times, so \mathrm{ex}(n,\mathcal{F}_{T,2}^{q})\leq\mathrm{ex}(n,T_{R}^{q})=O_{q}(n), proving the result. ∎ This together with our main theorem quickly gives our results related to the diameter of T . Proof of Theorem 1.7 . Since \mathrm{ex}(n,T,\mathcal{F})=o(n^{k+1}) , Theorem 1.3 gives a q such that every graph which is \mathcal{F} -free is also \mathcal{F}_{T,k+1}^{q} -free, and Theorem 1.3 also implies that \mathrm{ex}(n,T,\mathcal{F})=O(\mathrm{ex}(n,\mathcal{F})^{k})=O(\mathrm{ex}(n,\mathcal{F}_{T,k+1}^{q})^{k})=(n^{k+\frac{k(k-1)}{d-k}}), with this last step using Proposition 2.4 . ∎ Our next corollary relies on the fact that trees either have many leaves or large diameter. This statement can be made precise through the following result, which is a slight weakening of a statement from [ 20 ] . Lemma 2.5 ( [ 20 ] ) . If T is a tree with \ell leaves and diameter d , then v(T)\leq\frac{1}{2}\ell d . Proof of Theorem 1.8 . Let \ell and d denote the number of leaves and the diameter of T . If \mathrm{ex}(n,T,\mathcal{F})=O(n^{\ell}) then \mathrm{ex}(n,T,\mathcal{F})=\Theta(n^{k}) for some integer k by Corollary 1.6 , giving the result. We may thus assume that this is not the case, and since \mathrm{ex}(n,T,\mathcal{F})=O(n^{(\epsilon v(T))^{1/3}}) , this with Lemma 2.5 implies (\epsilon v(T))^{1/3}>\ell\geq 2v(T)/d , and hence d/2\geq v(T)/(\epsilon v(T))^{1/3}. (2) Now let k be the largest integer such that \mathrm{ex}(n,T,\mathcal{F})=\Omega(n^{k}) . Since \mathrm{ex}(n,T,\mathcal{F})=O(n^{(\epsilon v(T))^{1/3}}) , we have k\leq(\epsilon v(T))^{1/3}\leq v(T)/(\epsilon v(T))^{1/3}\leq d/2, (3) with this second inequality using the fact that \epsilon\leq 1 . Because we do not have \mathrm{ex}(n,T,\mathcal{F})=\Omega(n^{k+1}) , Theorem 1.3 implies there exists some q such that every \mathcal{F} -free graph is \mathcal{F}_{T,k+1}^{q} -free and also that \mathrm{ex}(n,T,\mathcal{F})=O(\mathrm{ex}(n,\mathcal{F})^{k})=O(\mathrm{ex}(n,\mathcal{F}_{T,k+1}^{q})^{k}). We claim now that \mathrm{ex}(n,\mathcal{F}_{T,k+1}^{q})^{k}=O(n^{k+\frac{2k^{2}}{d}}). (4) Indeed, this is trivial if k=0 . If k\geq 1 , then because d\geq 2k by ( 3 ), we have by Proposition 2.4 that \mathrm{ex}(n,\mathcal{F}_{T,k+1}^{q})^{k}=O(n^{k+\frac{k(k-1)}{d-k}})=O(n^{k+\frac{2k^{2}}{d}}) with this last step using d\geq 2k , and k-1\leq k . Thus ( 4 ) always holds. By our bounds on d and k from ( 2 ) and ( 3 ) we have \frac{2k^{2}}{d}\leq\frac{k^{2}(\epsilon v(T))^{1/3}}{v(T)}\leq\epsilon, which together with ( 4 ) gives \mathrm{ex}(n,T,\mathcal{F})=O(n^{k+\epsilon}) as desired. ∎ We now prove our final application. Proof of Corollary 1.9 . Given r\in\mathbb{R}_{\geq 0}\setminus\mathbb{Z} , we may write r=\lfloor r\rfloor+2\epsilon for 0<\epsilon<1/2 . We claim that for every tree T with v(T)\geq\epsilon^{-1}r^{3} there exists no family \mathcal{F} with \mathrm{ex}(n,T,\mathcal{F})=\Theta(n^{r}) . Indeed, assume for contradiction that such a T,\mathcal{F} existed. Since r\leq(\epsilon v(T))^{1/3} , Theorem 1.8 implies that there exists some integer k with \mathrm{ex}(n,T,\mathcal{F}) lying between \Omega(n^{k}) and O(n^{k+\epsilon}) . But \Theta(n^{r}) does not lie within this range for any integer k , a contradiction. We conclude that only the finitely many trees T with v(T)<\epsilon^{-1}r^{3} can have \mathrm{ex}(n,T,\mathcal{F})=\Theta(n^{r}) . ∎ 3 Generalizaed Turán Preliminaries Here we establish some preliminary results needed to prove our generalized Turán Theorems 1.3 and 1.10 , the most important of which is our Edge Helly Theorem, Theorem 1.11 . Proof of Theorem 1.11 . Recall that we wish to prove that if T is a tree, if \mathcal{T} is a collection of subtrees of T , and if k\geq 0 is an integer; then if for all subcollections \mathcal{T}^{\prime}\subseteq\mathcal{T} of size at most k+1 there exists a set of at most k edges E^{\prime}\subseteq E(T) which pierces \mathcal{T}^{\prime} (meaning every T^{\prime}\in\mathcal{T}^{\prime} has a vertex used in one of the edges of E^{\prime} ), then there exists a set of at most k edges E\subseteq E(T) which pierces \mathcal{T} . Assume for contradiction that this is false for some T,\mathcal{T},k , and among all such counterexamples we choose one with v(T) as small as possible and subject to this k as small as possible. The result is trivial for k=0 and if v(T)=1 or v(T)=2 , so we may assume that k\geq 1 and v(T)\geq 3 . Let x be any leaf of T and y the unique neighbor of x . Let T_{x} denote the (single vertex) subtree with V(T_{x})=\{x\} . We break our argument up into two cases based on if T_{x} is in \mathcal{T} . Case 1: T_{x}\in\mathcal{T} . Define \mathcal{T}^{-}_{x,y}:=\{T^{\prime}\in\mathcal{T}:x,y\notin V(T^{\prime})\} . We claim that every \mathcal{T}^{\prime}\subseteq\mathcal{T}^{-}_{x,y} of size at most k can be pierced by a set of at most k-1 edges. Indeed, for any such collection we have by hypothesis that \{T_{x}\}\cup\mathcal{T}^{\prime} can be pierced by a set E^{\prime} of at most k edges. One of these edges must necessarily be xy since this is the unique edge containing x , and since xy is disjoint from every element of \mathcal{T}^{\prime}\subseteq\mathcal{T}^{-}_{x,y} , we have that E^{\prime}\setminus\{xy\} is a set of at most k-1 edges piercing \mathcal{T}^{\prime} . This proves the claim, and because of our choice of minimal counterexample, this claim implies that \mathcal{T}^{-}_{x,y} can be pierced by some set E of at most k-1 edges. It is easy to check then that E\cup\{xy\} is a set of at most k edges which pierces \mathcal{T} , proving the result. Case 2: T_{x}\notin\mathcal{T} . In this case we define a new collection \mathcal{T}_{-x}=\{T^{\prime}-x:T^{\prime}\in\mathcal{T}\} which we view as a subtree system of T-x . We claim that every \mathcal{T}^{\prime}\subseteq\mathcal{T}_{-x} of size at most k+1 can be pierced by a set of at most k edges of T-x . Indeed, if say \mathcal{T}^{\prime}=\{T_{1}-x,\ldots,T_{\ell}-x\} for some \ell\leq k+1 , then by hypothesis we know there exists a set E^{\prime} of at most k edges of T which pierce \{T_{1},\ldots,T_{\ell}\} . If E^{\prime}\subseteq T-x then E^{\prime} will also pierce \mathcal{T}^{\prime} , so the only possible issue is if xy\in E^{\prime} . In this case if we let x^{\prime} denote any neighbor of y in T other than x (which exists since y is adjacent to a leaf and v(T)\geq 2 ), then the edge set (E^{\prime}\cup\{x^{\prime}y\})\setminus\{xy\} will pierce \mathcal{T}^{\prime} since none of these trees contain x by assumption, proving the claim. Since we are working with a minimal counterexample, we conclude that there exists some set E of at most k edges of T-x which pierces all of \mathcal{T}_{-x} . Because T_{x}=\{x\}\notin\mathcal{T} these edges E will pierce \mathcal{T} as well. ∎ Our remaining preliminaries will be written in terms of general graphs H , though we will only apply these in the case when H is a tree. We establish some results around generalized Turán numbers, beginning with an observation which motivates the technical definition of \mathcal{F}_{H,k}^{q} and which can be viewed as a weak version of our main result Theorem 1.3 . Proposition 3.1 . For every graph H , integer k\geq 0 , and family of graphs \mathcal{F} , we either have \mathrm{ex}(n,H,\mathcal{F})=\Omega_{H,k}(n^{k+1}) or there exists an integer q such that every \mathcal{F} -free graph is also \mathcal{F}_{H,k+1}^{q} -free. In particular, either \mathrm{ex}(n,H,\mathcal{F})=\Omega_{H,k}(n^{k+1}) or \mathrm{ex}(n,H,\mathcal{F})\leq\mathrm{ex}(n,H,\mathcal{F}_{H,k+1}^{q}) . Proof. Let H , k\geq 0 , and \mathcal{F} be given. For R\subseteq V(H) , let w(R) denote the number of connected components of H-R . We consider two cases. Case 1: for every R\subsetneq V(H) with w(R)\geq k+1 , there exists some integer q(R) such that the family \mathcal{F} contains a graph which is a subgraph of H_{R}^{q(R)} . Letting q:=\max_{R}q(R) , this means that any \mathcal{F} -free graph is also \mathcal{F}_{H,k+1}^{q} -free as desired. Case 2: there exists R\subsetneq V(H) with w(R)\geq k+1 such that \mathcal{F} does not contain any subgraph of H_{R}^{q} for any q . Let n^{\prime}=\lfloor{n/|V(H)|}\rfloor and consider G=H_{R}^{n^{\prime}} . This graph has at most n vertices and is \mathcal{F} -free by hypothesis. Moreover, H_{R}^{n^{\prime}} contains at least (n^{\prime})^{k+1}=\Omega_{H,k}(n^{k+1}) copies of H , namely by taking the copies which use R and for each of the at least k+1 components of H-R chooses one of the n^{\prime} copies making up H_{R}^{n^{\prime}} to embed into. This implies \mathrm{ex}(n,H,\mathcal{F})=\Omega(n^{k+1}) , proving the result. ∎ To prove our main results, it will be convenient to shift from counting copies of H in G and instead count monomorphisms of H into G . Definition 3 . Given graphs H and G , we say that a map \phi:V(H)\to V(G) is a monomorphism of H into G if \phi is both injective and a homomorphism. We let \mathrm{Mon}(H,G) denote the set of monomorphisms of H into G and we let \mathrm{mon}(H,G):=|\mathrm{Mon}(H,G)| . Given a monomorphism \phi\in\mathrm{Mon}(H,G) the graph-image of \phi is the copy H^{*} of H in G with vertex set V(H^{*})=\phi(V(H)) and such that xy\in E(H) if and only if \phi(x)\phi(y)\in E(H^{*}) . The following shows that counting monomorphisms is equivalent to counting copies. Observation 3.2 . For every pair of graphs H and G , the number of copies of H in G equals \frac{\mathrm{mon}(H,G)}{\operatorname{aut}(H)}, where \operatorname{aut}(H) denotes the size of the automorphism group of H . This follows from the fact that a copy of H in G is a subgraph of G which is isomorphic to H , each such copy giving rise to exactly \mathrm{aut}(H) monomorphisms. Because of this observation, we will often bound the number of copies of a graph H by instead bounding \mathrm{mon}(H,G) . The following concept will be useful to work with, where here the set of maps \Phi we use will always be collections of monomorphisms. Definition 4 . We say that a set of maps \Phi with the same domain S is distinguishing if for all distinct x,y\in S , we have \phi(x)\neq\phi^{\prime}(y) for all \phi,\phi^{\prime}\in\Phi . Equivalently \{\phi(x):\phi\in\Phi\}\cap\{\phi(y):\phi\in\Phi\}=\emptyset . Note that if \Phi is distinguishing then so is any subset \Phi^{\prime}\subseteq\Phi as well as its set of restrictions \{\phi|_{S^{\prime}}:\phi\in\Phi\} for any S^{\prime}\subseteq S . The main facts we’ll need about these are the following. Observation 3.3 . Let H,G be graphs and \Phi\subseteq\mathrm{Mon}(H,G) a distinguishing set of monomorphisms. (a) For all X\subseteq V(H) , if \phi,\phi^{\prime}\in\Phi satisfy \phi(X)=\phi^{\prime}(X) , then \phi(\hat{x})=\phi^{\prime}(\hat{x}) for all \hat{x}\in X . (b) There exists a partition \bigcup_{\hat{x}\in V(T)}V_{\hat{x}} of V(G) such that \{\phi(\hat{x}):\phi\in\Phi\}\subseteq V_{\hat{x}} for all \hat{x}\in V(H) . Proof. For (a) , given \hat{x}\in X , since \phi(X)=\phi^{\prime}(X) , we must have \phi(\hat{x})=\phi^{\prime}(\hat{y}) for some \hat{y}\in X , but then since \Phi is distingushing, we have \hat{x}=\hat{y} , so \phi(\hat{x})=\phi^{\prime}(\hat{x}) . For (b) , the sets \{\phi(\hat{x}):\phi\in\Phi\} are disjoint for distinct \hat{x} since \Phi is distinguishing and as such one can partition V(G) in any way that preserves \{\phi(\hat{x}):\phi\in\Phi\}\subseteq V_{\hat{x}} for all \hat{x}\in V(H) . ∎ We also have the following useful result. Lemma 3.4 . For any graphs H,G , there exists a set of distinguishing monomorphisms \Phi\subseteq\mathrm{Mon}(H,G) with |\Phi|\geq v(H)^{-v(H)}\mathrm{mon}(H,G) . Proof. Randomly partition V(G) into sets \{V_{\hat{x}}:\hat{x}\in V(T)\} by including each vertex in V(G) into each of these sets uniformly and independently at random. Let \Phi\subseteq\mathrm{Mon}(H,G) be the collection of \phi\in\mathrm{Mon}(H,G) with the property that \phi(\hat{x})\in V_{\hat{x}} for all \hat{x}\in V(H) . Because \Pr[\phi\in\Phi]=v(H)^{-v(H)} , we have \mathbb{E}[|\Phi|]=v(H)^{-v(H)}\mathrm{mon}(H,G) by linearity of expectation, and in particular there exists some choice of V_{\hat{x}} sets such that |\Phi|\geq v(H)^{-v(H)}\mathrm{mon}(H,G) . ∎ Finally, we need the following. Lemma 3.5 . For every graph H and integer q\geq 2 , there exists some integer {q_{\star}}={q_{\star}}(H,q) with {q_{\star}}\geq q such that if G is a graph and if \Phi\subseteq\mathrm{Mon}(H,G) satisfies |\Phi|\geq{q_{\star}} , then there exists a set R\subsetneq V(H) and distinct maps \phi_{1},\ldots,\phi_{q}\in\Phi such that for all i\neq j , we have \phi_{i}(\hat{x})=\phi_{j}(\hat{y}) if and only if \hat{x}=\hat{y} and \hat{x}\in R . In other words, the maps \phi_{1},\ldots,\phi_{q} are such that the union of their graph-images is a copy of H_{R}^{q} in G . Proof. This result is a consequence of the Erdős-Rado sunflower lemma [ 23 ] , which states 1 1 1 We note in passing that it is a major open problem to improve upon the bounds of the Erdős-Rado sunflower lemma, though we will only need that some finite bound exists. For a more thorough treatment of this result and best known bounds we refer the reader to [ 2 ] . that if \mathcal{H} is an r -uniform hypergraph with |E(\mathcal{H})|\geq k!(r-1)^{k} , then there exist edges e_{1},\ldots,e_{k}\in E(\mathcal{H}) and a set K\subseteq V(\mathcal{H}) such that e_{i}\cap e_{j}=K for every i\neq j . We will ultimately apply this result with r:=v(H) and k:=q\cdot v(H)! , with us in the end proving the lemma for the value {q_{\star}}(H,G):=v(H)!\cdot k!(r-1)^{k} . Given a collection of at least {q_{\star}}(H,G) monomorphisms \Phi\subseteq\mathrm{Mon}(H,G) , we first take a subcollection \Phi^{\prime}\subseteq\Phi such that \phi(V(H))\neq\phi^{\prime}(V(H)) for all \phi,\phi^{\prime}\in\Phi^{\prime} . Since at most v(H)! monomorphisms can have the same image, we can find such a collection with |\Phi^{\prime}|\geq|\Phi|/v(H)!\geq k!(r-1)^{k} . Consider the r -uniform hypergraph \mathcal{H} with V(\mathcal{H})=V(G) and E(\mathcal{H})=\{\phi(V(H))\mid\phi\in\Phi^{\prime}\}. Note that |E(\mathcal{H})|=|\Phi^{\prime}| by the defining property of \Phi^{\prime} . By the sunflower lemma, there are k edges of \mathcal{H} , say \phi_{1}(V(H)),\dots,\phi_{k}(V(H)) , and a set K\subseteq V(G) such that \phi_{i}(V(H))\cap\phi_{j}(V(H))=K for all i\neq j . Let K=\{v_{1},v_{2},\dots,v_{t}\} , and associate to each \phi_{i} the tuple (\phi_{i}^{-1}(v_{1}),\phi_{i}^{-1}(v_{2}),\dots,\phi_{i}^{-1}(v_{t})) . Since the \phi_{i} ’s are injective and t\leq v(H) , there are at most v(H)! possible tuples, so by pigeonhole there must exist a collection of at least k/v(H)!=q of the \phi_{i} ’s which correspond to the same tuple. Without loss of generality we can assume that \phi_{1},\dots,\phi_{q} have this property. Let R:=\phi_{1}^{-1}(K) . This gives for i,j\in[q] with i\neq j that \phi_{i}(\hat{x})=\phi_{j}(\hat{y}) if and only if \hat{x}=\hat{y} and \hat{x}\in R . Furthermore, R\neq V(H) since \phi_{1}\neq\phi_{2} , but \phi_{1} and \phi_{2} agree on R . Thus, R along with \phi_{1},\ldots,\phi_{q} satisfy the conditions of the lemma. ∎ 4 Proof of Theorem 1.3 Our main goal for this section will be to prove the following technical result. Theorem 4.1 . If T\neq K_{1} is a tree and if k\geq 0 and q\geq 2 are integers, then any n -vertex graph G which is \mathcal{F}_{T,k+1}^{q} -free contains at most O(e(G)^{k}) copies of T . Our motivation for this is that it quickly implies Theorem 1.3 . Proof of Theorem 1.3 . If there does not exist a value of q such that every \mathcal{F} -free graph is \mathcal{F}_{T,k+1}^{q} -free, then Proposition 3.1 implies \mathrm{ex}(n,T,\mathcal{F})=\Omega_{T,k}(n^{k+1}) as desired. Now let us assume there is such a q , and assume for the moment that q\geq 2 . By taking G to be an \mathcal{F} -free graph with \mathrm{ex}(n,T,\mathcal{F}) copies of T , we note that G is \mathcal{F}_{T,k+1}^{q} -free as well by the defining property of q , so Theorem 4.1 gives \mathrm{ex}(n,T,\mathcal{F})=O(e(G)^{k})=O(\mathrm{ex}(n,\mathcal{F})^{k}), The only remaining case is q=1 , which follows from the case q=2 and monotonicity. ∎ Proof Intuition for Theorem 4.1 . The statement of Theorem 4.1 suggests how it might be proved, namely by showing that in any \mathcal{F}_{T,k+1}^{q} -free graph G , every copy of T contains a set of k edges E with the property that E is contained in at most O(1) copies of T in G . \bullet \bullet \bullet \bullet \bullet \bullet \bullet \bullet \bullet \bullet \bullet Figure 2 : A depiction of (P_{5})_{\{\hat{x}_{3},\hat{x}_{4}\}}^{3} . Observe that each copy of P_{5} in this graph can be identified by specifying which edges plays the role of \hat{x}_{1}\hat{x}_{2} and \hat{x}_{4}\hat{x}_{5} . For example, consider P_{5} the path graph on \hat{x}_{1}\hat{x}_{2}\hat{x}_{3}\hat{x}_{4}\hat{x}_{5} and G:=(P_{5})_{\{\hat{x}_{3},\hat{x}_{4}\}}^{n} (i.e. G is obtained by taking n copies of P_{5} which all agree on the edge \hat{x}_{3}\hat{x}_{4} and are otherwise disjoint; see Figure 2 ). Here each copy P of P_{5} in G can be uniquely identified by specifying the edges of G which play the role of \hat{x}_{1}\hat{x}_{2} and \hat{x}_{4}\hat{x}_{5} in P , implying that G contains at most e(G)^{2} copies of P_{5} . The same argument works 2 2 2 Technically specifying \hat{x}_{2}\hat{x}_{3} and \hat{x}_{4}\hat{x}_{5} only specifies all of the “canonical” P_{5} ’s, i.e. the ones that go from left to right. However, by considering random 5-partitions of the host graph G one can reduce the problem of upper bounding copies of P_{5} in G with upper bounding “canonicall” copies of P_{5} . if we alternatively specified which edges play the role of \hat{x}_{2}\hat{x}_{3} and \hat{x}_{4}\hat{x}_{5} in P . In the proof above, it is critical that we specify the edge of G playing the role of \hat{x}_{4}\hat{x}_{5} , as even if we specify every other edge of a copy of P_{5} , there would still exist n ways to extend these specified edges into distinct copies of P_{5} in G . More generally, the edge set E we wish to choose for each copy must “intersect” with every subtree which has “many options” for being extended. More precisely, for each monomorphism \phi:V(T)\to V(G) , we wish to define a subtree system \mathcal{T}_{\phi} of T whose elements have “many extensions” with respect to \phi , in the sense that for each T^{\prime}\in\mathcal{T}_{\phi} , there exist many monomorphisms \phi^{\prime} which agree with \phi outside of T^{\prime} (i.e. there exist many ways of changing how \phi maps T^{\prime} while maintaining that \phi is a monomorphism). For example, if G=(P_{5})^{n}_{\{\hat{x}_{3},\hat{x}_{4}\}} then for every \phi we will define \mathcal{T}_{\phi} to consist of the subtrees which either contain \hat{x}_{1}\hat{x}_{2} or \hat{x}_{5} , i.e. \mathcal{T}_{\phi}=\{\hat{x}_{1}\hat{x}_{2},\hat{x}_{1}\hat{x}_{2}\hat{x}_{3},\hat{x}_{1}\hat{x}_{2}\hat{x}_{3}\hat{x}_{4},\hat{x}_{1}\hat{x}_{2}\hat{x}_{3}\hat{x}_{4}\hat{x}_{5},\hat{x}_{2}\hat{x}_{3}\hat{x}_{4}\hat{x}_{5},\hat{x}_{3}\hat{x}_{4}\hat{x}_{5},\hat{x}_{4}\hat{x}_{5},\hat{x}_{5}\}. More generally, if G=T_{R}^{n} , then \mathcal{T}_{\phi} will consist of the subtrees that contain a connected component of T-R . The key insight about working with these sets \mathcal{T}_{\phi} is that whatever edge set E we ultimately choose to identify each copy \phi with, this set E must have the property that every T^{\prime}\in\mathcal{T}_{\phi} has \phi(V(T^{\prime})) intersecting with an edge in E . Indeed, if this were not the case then E would necessarily be contained in “many” copies of T , namely those which agree with \phi outside of the subtree T^{\prime}\in\mathcal{T}_{\phi} which does not intersect with E . Ultimately then, we require a sufficient condition to guarantee that a subtree system \mathcal{T} can be pierced by a small set of edges, which motivates the need for our Edge Helly Theorem, Theorem 1.11 . 4.1 Formal Details We begin by collecting some technical definitions that will be used throughout this section and the next. Our first definitions precisely characterize which subtrees T^{\prime}\subseteq T have “many extensions”, as mentioned in the proof sketch above. Definition 5 . Let T be a tree, G a graph, \Phi\subseteq\mathrm{Mon}(T,G) a collection of monomorphisms and C>0 a constant. Given a subtree T^{\prime}\subseteq T , define the neighborhood of T^{\prime} N(T^{\prime}):=\{\hat{x}\in V(T)\setminus V(T^{\prime}):N(\hat{x})\cap V(T^{\prime})\neq\emptyset\}. For S\subseteq V(G) we define the extendable set \Psi(T^{\prime},S;\Phi):=\{\phi|_{V(T^{\prime})}:\phi\in\Phi,\ \phi(N(T^{\prime}))=S\}. That is, \Psi is the restriction to T^{\prime} of all maps \phi\in\Phi which map N(T^{\prime}) to S , i.e. these are maps of T^{\prime} which can be extended to a map of T while acting on N(T^{\prime}) in a specified way. Finally, If \phi\in\Phi , then we define the set of highly extendable subtrees , \mathcal{T}_{\phi,\Phi,C} to be the set of subtrees T^{\prime}\subseteq T such that |\Psi(T^{\prime},\phi(N(T^{\prime}));\Phi)|\geq C . Our next set of definitions gives a generalization of the notion of piercing which may be of independent interest. Definition 6 . Given a tree T , a set of distinguishing monomorphisms \Phi\subseteq\mathrm{Mon}(T,G) , and some \phi\in\Phi , we say a set of vertices \widehat{W}\subseteq V(T) (\phi,\Phi) -pseudo-pierces a subtree T^{\prime}\subseteq T if there exists a vertex \hat{x}\in V(T^{\prime}) such that |\{\phi^{\prime}(\hat{x}):\phi^{\prime}\in\Phi,\ \phi^{\prime}(\widehat{W})=\phi(\widehat{W})\}|\leq v(T). Similarly, we say \widehat{W} (\phi,\Phi) -pseudo-pierces a subtree system \mathcal{T} if it (\phi,\Phi) -pseudo-pierces every T^{\prime}\in\mathcal{T} . Given a set of edges \widehat{E}\subseteq E(T) , we let V(\widehat{E}) denote the set of vertices of T incident to an edge of \widehat{E} . If \widehat{E} is a set of at most a edges and if \widehat{U}\subseteq V(T) a set of at most b vertices, we say that (\widehat{E},\widehat{U}) is an (a,b,\phi,\Phi) -pseudo-piercing set for \mathcal{T} if V(\widehat{E})\cup\widehat{U} (\phi,\Phi) -pseudo-pierces \mathcal{T} . Similarly we say that (\widehat{E},\widehat{U}) is an (a,b) -piercing set for \mathcal{T} if V(\widehat{E})\cup\widehat{U} pierces \mathcal{T} . It will be useful to record the easy fact that piercing implies pseudo-piercing which we will implicitly use throughout. Lemma 4.2 . If T is a tree and if \widehat{W}\subseteq V(T) pierces some subtree T^{\prime}\subseteq T , then \widehat{W} (\phi,\Phi) -pseudo-pierces T^{\prime} for any set of distinguishing monomorphisms \Phi\subseteq\mathrm{Mon}(T,G) and \phi\in\Phi . In particular, (a,b) -piercing sets are (a,b,\phi,\Phi) -pseudo-piercing sets. Indeed, this follows because if \Phi is distinguishing, we have by 3.3 (a) that any \hat{x}\in\widehat{W}\cap V(T^{\prime}) (which exists by assumption of piercing) has |\{\phi^{\prime}(\hat{x}):\phi^{\prime}\in\Phi,\ \phi^{\prime}(\widehat{W})=\phi(\widehat{W})\}|\leq|\{\phi^{\prime}(\hat{x}):\phi^{\prime}\in\Phi,\ \phi^{\prime}(\hat{x})=\phi(\hat{x})\}|=1, proving this (\phi,\Phi) -pseudo-pierces T^{\prime} . The notion of psuedo-piercing is not needed to prove our main result of this section, Theorem 4.1 . However, it will be necessary in Section 5 , and so we present our results here in terms of the general notion of pseudo-piercing so that we may use them later on and in potential future works. As hinted at in the proof intuition above, our goal will be to show that the families \mathcal{T}_{\phi,\Phi,C} can be pierced by a small number of edges using the Edge Helly Theorem. We will then use this in conjunction with the following to show that this implies G contains few copies of T . Proposition 4.3 . Let T\neq K_{1} be a tree, G a graph, \Phi\subseteq\mathrm{Mon}(T,G) a set of distinguishing monormphisms, and C,a,b non-negative integers. If \Phi^{\prime}\subseteq\Phi is such that for every \phi\in\Phi^{\prime} , the collection \mathcal{T}_{\phi,\Phi,C} has an (a,b,\phi,\Phi) -pseudo-piercing set, then |\Phi^{\prime}|=O_{C}(e(G)^{a}v(G)^{b}). Proof. The result is trivial if e(G)=0 since e(T)\geq 1 , so we may assume e(G)>0 from now on. For each \phi\in\Phi , let \widehat{E}_{\phi},\widehat{U}_{\phi} be the set of at most a edges and at most b vertices of T such that V(\widehat{E}_{\phi})\cup\widehat{U}_{\phi} is a (\phi,\Phi) -pseudo-piercing set for \mathcal{T}_{\phi,\Phi,C} , and define E_{\phi}:=\{\phi(\hat{x})\phi(\hat{y}):\hat{x}\hat{y}\in\widehat{E}_{\phi}\}, and U_{\phi}:=\phi(\widehat{U}_{\phi})=\{\phi(\hat{x}):\hat{x}\in\widehat{U}_{\phi}\}. Observe that E_{\phi} is a set of at most a edges of G since \phi is a homomorphism and similarly that U_{\phi} is a set of at most b vertices of G . We aim to show that for each set of at most a edges E\subseteq E(G) and each set of at most b vertices U\subseteq V(G) , the number of \phi\in\Phi^{\prime} with E_{\phi}=E and U_{\phi}=U is O(1) , from which it will follow that |\Phi^{\prime}|=O(e(G)^{a}v(G)^{b}) since there are at most O(e(G)^{a}v(G)^{b}) choices for E,U (here we implicitly use the assumption e(G),v(G)>0 ). From now on we fix some E,U as above. Define \Phi^{\prime}_{E,U}:=\{\phi\in\Phi^{\prime}:V(E)\cup U\subseteq\phi(V(T))\}, and \widehat{V}_{E,U}:=\{\hat{x}\in V(T):|\{\phi(\hat{x}):\phi\in\Phi_{E,U}^{\prime}\}|\leq v(T)\}. The motivation for this is the following. Claim 4.4 . If \phi\in\Phi^{\prime} is such that E_{\phi}=E and U_{\phi}=U , then for every T^{\prime}\in\mathcal{T}_{\phi,\Phi,C} , we have V(T^{\prime})\cap\widehat{V}_{E,U}\neq\emptyset . Proof. By hypothesis of the proposition, for every T^{\prime}\in\mathcal{T}_{\phi,\Phi,C} there exists \hat{x}\in V(T^{\prime}) such that \left|\left\{\psi(\hat{x}):\psi\in\Phi,\ \psi\left(V(\widehat{E}_{\phi})\cup\widehat{U}_{\phi}\right)=\phi\left(V(\widehat{E}_{\phi})\cup\widehat{U}_{\phi}\right)\right\}\right|\leq v(T). (5) Note that \phi\left(V(\widehat{E}_{\phi})\cup\widehat{U}_{\phi}\right)=V(E_{\phi})\cup U_{\phi}=V(E)\cup U . This, ( 5 ), and the fact that \Phi^{\prime}\subseteq\Phi gives \left|\left\{\psi(\hat{x}):\psi\in\Phi^{\prime},\ \psi\left(V(\widehat{E}_{\phi})\cup\widehat{U}_{\phi}\right)=V(E)\cup U\right\}\right|\leq v(T). (6) Since \Phi^{\prime} is distinguishing, for any \psi\in\Phi^{\prime} , having \psi(V(\widehat{E}_{\phi})\cup\widehat{U}_{\phi})=V(E)\cup U is equivalent to having V(E)\cup U\subseteq\psi(V(T)) . Thus ( 6 ) is equivalent to |\{\psi(\hat{x}):\psi\in\Phi^{\prime}_{E,U}\}|\leq v(T) , which means that \hat{x}\in\widehat{V}_{E,U} by definition. ∎ Let T^{\prime}_{1},\ldots,T^{\prime}_{m} denote the connected components of T-\widehat{V}_{E,U} . The final fact we need is the following. Claim 4.5 . If there exists some \phi\in\Phi^{\prime} such that E_{\phi}=E and U_{\phi}=U , then for all j , |\Psi(T^{\prime}_{j},\phi(N(T^{\prime}_{j}));\Phi)|1 and every \phi\in\Phi_{i} , there does not exist an (a,b,\phi,\Phi_{i-1}) -pseudo-piercing set for \mathcal{T} . (S5) We have |\Phi_{t}|\geq(C^{\prime\prime})^{-1}\mathrm{mon}(T,G) . For such a sequence we say that \mathcal{T} is the associated subtree system and that C_{1},\ldots,C_{t-1} are the associated integers. Crucially, we can prove that every graph either has such a refinement sequence or few copies of T . Lemma 5.2 . For every tree T and integers a,b,C^{\prime} , there exists an integer C^{\prime\prime} such that every graph G either has an (a,b,C^{\prime},C^{\prime\prime},T) -refinement sequence or has at most C^{\prime\prime}e(G)^{a}v(G)^{b} copies of T . Proof. If \mathrm{Mon}(T,G) is empty then trivially G has at most C^{\prime\prime}e(G)^{a}v(G)^{b} copies of T , so we assume \mathrm{Mon}(T,G) is non-empty. Let \Phi^{\prime}_{1} be the large family of distinguishing monomorphisms guaranteed from Lemma 3.4 and let C^{\prime}_{1}:=C^{\prime} . Iteratively given that we have defined \Phi^{\prime}_{i},C^{\prime}_{i} , we define the following set of objects: • Let \Psi_{i}^{\prime}\subseteq\Phi^{\prime}_{i} be the set of maps \phi such that \mathcal{T}_{\phi,\Phi_{i}^{\prime},C_{i}^{\prime}} has an (a,b,\phi,\Phi^{\prime}_{i}) -pseudo-piercing set and let \Phi^{\prime\prime}_{i}=\Phi^{\prime}_{i}\setminus\Psi_{i}^{\prime} . • For a subtree system \mathcal{T} , let \Phi^{\prime\prime}_{i,\mathcal{T}}\subseteq\Phi^{\prime\prime}_{i} denote the set of \phi which have \mathcal{T}_{\phi,\Phi_{i}^{\prime},C_{i}^{\prime}}=\mathcal{T} . • By the pigeonhole principle, there exists some \mathcal{T} such that |\Phi^{\prime\prime}_{i,\mathcal{T}}|\geq 2^{-2^{v(T)}}|\Phi^{\prime\prime}_{i}| . We let \mathcal{T}_{i} be any such family and define \Phi^{\prime}_{i+1}:=\Phi^{\prime\prime}_{i,\mathcal{T}_{i}} , and C^{\prime}_{i+1}:=\max_{T^{\prime}\subseteq T}{q_{\star}}(T^{\prime},C^{\prime}_{i}) , where the maximum goes over all subtrees of T , and {q_{\star}}(T^{\prime},C^{\prime}_{i}) is the constant guaranteed by Lemma 3.5 . We observe the following. Claim 5.3 . If \Phi^{\prime\prime}_{i+1}\neq\emptyset then \mathcal{T}_{i+1}\subseteq\mathcal{T}_{i} . Proof. By definition, we have \Phi^{\prime\prime}_{i+1,\mathcal{T}_{i+1}}\subseteq\Phi^{\prime\prime}_{i+1}\subseteq\Phi^{\prime}_{i+1}=\Phi^{\prime\prime}_{i,\mathcal{T}_{i}}. (7) By assumption we have \Phi^{\prime\prime}_{i+1}\neq\emptyset , which further implies that \Phi^{\prime\prime}_{i+1,\mathcal{T}_{i+1}}\neq\emptyset , so there exists some \phi^{*}\in\Phi^{\prime\prime}_{i+1,\mathcal{T}_{i+1}} . By ( 7 ), we also have \phi^{*}\in\Phi^{\prime\prime}_{i,\mathcal{T}_{i}} . Thus, by definition, \mathcal{T}_{i+1}=\mathcal{T}_{\phi^{*},\Phi^{\prime}_{i+1},C^{\prime}_{i+1}} and \mathcal{T}_{i}=\mathcal{T}_{\phi^{*},\Phi^{\prime}_{i},C^{\prime}_{i}} . Observe that for any arbitrary sets of monomorphisms \Psi^{\prime}\subseteq\Psi and integers p^{\prime}\geq p , we have \mathcal{T}_{\psi,\Psi^{\prime},p^{\prime}}\subseteq\mathcal{T}_{\psi,\Psi,p} for any \psi\in\Psi^{\prime} simply by definition of these subtree systems. Using this, we note that since \Phi^{\prime}_{i+1}\subseteq\Phi^{\prime}_{i} and C^{\prime}_{i+1}\geq C^{\prime}_{i} , we have that \mathcal{T}_{\phi^{*},\Phi^{\prime}_{i+1},C^{\prime}_{i+1}}\subseteq\mathcal{T}_{\phi^{*},\Phi^{\prime}_{i},C^{\prime}_{i}} . Putting everything together, we have \mathcal{T}_{i+1}=\mathcal{T}_{\phi^{*},\Phi^{\prime}_{i+1},C^{\prime}_{i+1}}\subseteq\mathcal{T}_{\phi^{*},\Phi^{\prime}_{i},C^{\prime}_{i}}=\mathcal{T}_{i}. ∎ We also seek to understand the sizes of the \Phi^{\prime}_{i} sets. Claim 5.4 . If i is such that |\Phi^{\prime}_{j}|\geq 2|\Psi_{j}^{\prime}| for all 1\leq j\leq i , then |\Phi_{i+1}^{\prime}|\geq 2^{-i-i2^{v(T)}}|\Phi^{\prime}_{1}| . Proof. Note that if |\Phi^{\prime}_{j}|\geq 2|\Psi_{j}^{\prime}| then |\Phi^{\prime\prime}_{j}|\geq 2^{-1}|\Phi^{\prime}_{j}| , and so |\Phi_{j+1}^{\prime}|=|\Phi^{\prime\prime}_{j,\mathcal{T}_{j}}|\geq 2^{-2^{v(T)}}|\Phi^{\prime\prime}_{j}|\geq 2^{-2^{v(T)}}\cdot 2^{-1}|\Phi^{\prime}_{j}|. The stated bound then follows by induction. ∎ Now if there’s some 1\leq i\leq v(T)2^{2^{v(T)}} with |\Phi^{\prime}_{i}|<2|\Psi_{i}^{\prime}| , say i^{\prime} is the smallest such i , then because |\Psi_{i^{\prime}}|=O(e(G)^{a}v(G)^{b}) by Proposition 4.3 and |\Phi^{\prime}_{i^{\prime}}|\geq 2^{-(i^{\prime}-1)-(i^{\prime}-1)2^{v(T)}}|\Phi^{\prime}_{1}|\geq 2^{-v(T)2^{2^{v(T)}}(1+2^{v(T)})}|\Phi^{\prime}_{1}| by the minimality of i^{\prime} and 5.4 ; and because |\Phi_{1}^{\prime}|=\Omega(\mathrm{mon}(T,G)) by construction, we in total conclude that \mathrm{mon}(T,G)=O(|\Phi_{1}^{\prime}|)=O(|\Phi^{\prime}_{i^{\prime}}|)=O(|\Psi^{\prime}_{i^{\prime}}|)=O(e(G)^{a}v(G)^{b}). Let C^{*} be an integer large enough that \mathrm{mon}(T,G)\leq C^{*}e(G)^{a}v(G)^{b} in this case. Then as long as we choose C^{\prime\prime}\geq C^{*} , G has few copies of T . As such, we may assume that no such i^{\prime} exists. With the above and Claim 5.4 , have that |\Phi^{\prime}_{i}|\geq 2^{-(i-1)-(i-1)2^{v(T)}}|\Phi^{\prime}_{1}|=\Omega(\mathrm{mon}(T,G)) (8) for all 1\leq i\leq v(T)2^{2^{v(T)}} . Since all of these sets are in particular non-empty, by 5.3 and the pigeonhole principle there exists some i^{*}1 and a map \phi\in\Phi_{j} , let \mathcal{L}_{\phi,j}:=\{\phi^{\prime}(\ell_{i^{*}}-1)\mid\phi^{\prime}\in\Phi_{j-1},\ \phi^{\prime}(r_{i^{*}}+1)=\phi(r_{i^{*}}+1)\}, and \mathcal{R}_{\phi,j}:=\{\phi^{\prime}(r_{i^{*}}+1)\mid\phi^{\prime}\in\Phi_{j-1},\ \phi^{\prime}(\ell_{i^{*}}-1)=\phi(\ell_{i^{*}}-1)\}. Claim 5.10 . If j>1 and \phi\in\Phi_{j} , then |\mathcal{L}_{\phi,j}|\geq t and |\mathcal{R}_{\phi,j}|\geq t . We emphasize that the proof of this claim is the only place in our argument where we rely on the more general notion of pseudo-piercing. Proof. Assume to the contrary that one of these sets is small. Case 1: |\mathcal{L}_{\phi,j}|j . By (S3) we can choose maps \psi^{(1)}_{j},\dots\psi^{(C^{\prime})}_{j}\in\Psi(T_{i^{*}},\{u_{j},v_{j}\},\Phi_{1}) with pairwise-disjoint images. At most \left|\bigcup_{i=j+1}^{t}V(\theta_{i})\right|=1+(t-j)(1+q(b-1)) of these maps have images that intersect some \theta_{i} with i>j , and since C^{\prime}\geq q+1+(t-j)(1+q(b-1)) this means at least q of these maps avoid the \theta_{i} ’s, assume without loss of generality that \psi_{j}^{(1)},\dots,\psi_{j}^{(q)} are q maps whose images do not intersect \bigcup_{i=j+1}^{t}V(\theta_{i}) . The graph-images of these maps along with the vertices u_{i} and v_{i} constitute a copy of \theta_{q,b} in G , call it \theta_{j} , and note that \theta_{j} indeed intersects \theta_{j+1} only in u_{j}=u_{j+1} , and does not intersect any other \theta_{i} for i>j . We may continue this process until we have built \theta_{t},\theta_{t-1},\dots,\theta_{1} , which intersect in such a way to give a copy of \theta_{q,b,t} as desired. By hypothesis we have b=|V(T_{i^{*}})|+1\leq\frac{t-3}{k-1} and b\geq 2 , so by Lemma 5.8 this \theta_{q,b,t}\subseteq G contains an element of \mathcal{F}_{P_{t},k+1}^{q} as a subgraph, proving the result. ∎ The remainder of this subsection is dedicated to showing that a k -nice refinement sequence with the properties needed to apply Lemma 5.9 exists. In particular, we want to find a “small” tree T_{i^{*}} such that \ell_{i^{*}}-1\in V(T_{i^{*}-1}) and r_{i^{*}}+1\in V(T_{i^{*}+1}) . Before we can find such a tree, we need the following, which shows that T_{1} and T_{2k} must contain only the vertices 1 and t respectively. Lemma 5.11 . If G contains a k -nice (k-1,1,C^{\prime},C^{\prime\prime},P_{t}) -refinement sequence (\Phi_{t},\dots,\Phi_{1}) with (k,t,\mathcal{T}) -nice tuple (T_{1},T_{2},\dots,T_{2k}) such that C^{\prime}\geq 2q+t and such that \ell_{2}\neq 2 or r_{2k-1}\neq t-1 , then G contains a subgraph isomorphic to an element of \mathcal{F}_{P_{t},k+1}^{q} . Proof. By the symmetry of the problem it suffices to prove the conclusion under the assumption r_{2k-1}\neq t-1 . Consider any \phi\in\Phi_{t} . By (S3) together with the fact that each T_{i} is a minimal element of \mathcal{T}=\mathcal{T}_{\phi,\Phi_{t-1},C_{t-1}} and that C^{\prime}\geq 2q+t ; for each i there exist maps \psi_{i}^{(1)},\ldots,\psi_{i}^{(2q+t)}\in\Psi(T_{i},\phi(N(T_{i}));\Phi_{t-1}) with disjoint images. At most t of these maps have images which intersect with the image of \phi , so we may assume without loss of generality that \psi_{i}^{(1)},\ldots,\psi_{i}^{(2q)}\in\Psi(T_{i},\phi(N(T_{i}));\Phi_{t-1}) have images which are disjoint from the image of \phi . Let us define I:=\bigcup_{s=1}^{k}V(T_{2s-1}) . By 5.7 , we have that the sets V(T_{2s-1}) and V(T_{2s^{\prime}-1}) are disjoint for each s\neq s^{\prime} , s,s^{\prime}\in[k] , which will be crucial to make sure the maps we introduce below are well-defined. We break our proof into two cases based on the value of r_{2k-1} . Case 1: r_{2k-1}=t-2 . For each integer 1\leq p\leq q , we define a map \phi^{(p)}:V(P_{t})\to V(G) as follows: • For each integer 1\leq d\leq t-1 with d\notin I we let \phi^{(p)}(d)=\phi(d) . • For each integer 1\leq d\leq t-1 with d\in I , say with d\in V(T_{2s-1}) , we let \phi^{(p)}(d)=\psi_{2s-1}^{(p)}(d) . • We let \phi^{(p)}(t)=\psi_{2k-1}^{(q+p)}(t-2) . We emphasize this last step is well-defined since r_{2k-1}=t-2 implies t-2\in[\ell_{2k-1},r_{2k-1}]=V(T_{2k-1}) and hence lies in the domain of \psi^{(q+p)}_{2k-1} . T_{2k-1} T_{2k-3} T_{1} \ell_{2k-1} r_{2k-1} t-1 \ell_{2k-3} r_{2k-3} r_{1} … Figure 3 : Finding a copy of \mathcal{F}_{P_{t},k+1}^{q} in Case 1 of Lemma 5.11 . The graph-image of one \phi^{(p)} is shown in blue. Since \Phi_{t-1} is distinguishing and by our choices of the \psi_{i}^{(p)} ’s, the collection \{\phi^{(p)}\mid p\in[q]\} consists of monomorphisms of P_{t} into G such that each monomorphism agrees on the image of the set R:=V(P_{t})\setminus(I\cup\{t\}) , and otherwise the image is pairwise disjoint from any other map in the collection. Furthermore, we note that P_{t}-R will contain k+1 components; k of them being T_{2s-1} for s\in[k] , and one corresponding to the isolated vertex \{t\} . Thus, the graph-images of the \phi^{(p)} ’s constitute an element of \mathcal{F}^{q}_{P_{t},k+1} ; see Figure 3 for an illustration of this case. Case 2: r_{2k-1}\neq t-2 . This implies r_{2k-1}\leq t-3 since r_{2k-1}\neq t-1 by assumption and r_{2k-1}r_{i+1}-1 . If j is odd and i>j , then r_{j}\not\in I_{i} since r_{j}<\ell_{j+1}\leq\ell_{i}<\ell_{i}+1 . Similarly, if j is even and ir_{j-1}\geq r_{i+1}>r_{i+1}-1 . Finally if j is even and i\geq j , then \ell_{j}\not\in I_{i} since \ell_{j}\leq\ell_{i}<\ell_{i}+1 . Thus, I_{i} is indeed disjoint from S . We also claim that I_{i}\cap I_{j}=\emptyset for all i\neq j . Indeed if i,j are even integers with i