Helly Theorems for Generalized Turán Problems
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914455501144064 |
|---|---|
| author | English, Sean Spiro, Sam |
| author_facet | English, Sean Spiro, Sam |
| contents | 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 $Ω(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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_06357 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Helly Theorems for Generalized Turán Problems English, Sean Spiro, Sam Combinatorics 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 $Ω(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. |
| title | Helly Theorems for Generalized Turán Problems |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2604.06357 |