Helly Theorems for Generalized Turán Problems

Abstract

Given a graph $T$ and a family of graphs $\mathcal{F}$, the generalized Turán number $\mathrm{ex}(n,T,\mathcal{F})$ is the maximum number of copies of $T$ in an $n$-vertex $\mathcal{F}$-free graph. We prove a general theorem which states that for any tree $T$, any family $\mathcal{F}$, and any integer $k$, either $\mathrm{ex}(n,T,\mathcal{F})$ is at least $\hat{I}\text{c◯}(n^{k+1})$ or at most $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.

Some of these results appeared in version 1 of arXiv:2506.19061 which we are splitting into two papers