Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2301.05678 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910623804162048 |
|---|---|
| author | Kirsch, Rachel Nir, JD |
| author_facet | Kirsch, Rachel Nir, JD |
| contents | Generalized Turán problems ask for the maximum number of copies of a graph $H$ in an $n$-vertex, $F$-free graph, denoted by ex$(n,H,F)$. We show how to extend the new, localized approach of Bradač, Malec, and Tompkins to generalized Turán problems. We weight the copies of $H$ (typically taking $H=K_t$), instead of the edges, based on the size of the largest clique, path, or star containing the vertices of the copy of $H$, and in each case prove a tight upper bound on the sum of the weights. A consequence of our new localized theorems is an asymptotic determination of ex$(n,H,K_{1,r})$ for every $H$ having at least one dominating vertex and mex$(m,H,K_{1,r})$ for every $H$ having at least two dominating vertices. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2301_05678 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A localized approach to generalized Turán problems Kirsch, Rachel Nir, JD Combinatorics 05C35 Generalized Turán problems ask for the maximum number of copies of a graph $H$ in an $n$-vertex, $F$-free graph, denoted by ex$(n,H,F)$. We show how to extend the new, localized approach of Bradač, Malec, and Tompkins to generalized Turán problems. We weight the copies of $H$ (typically taking $H=K_t$), instead of the edges, based on the size of the largest clique, path, or star containing the vertices of the copy of $H$, and in each case prove a tight upper bound on the sum of the weights. A consequence of our new localized theorems is an asymptotic determination of ex$(n,H,K_{1,r})$ for every $H$ having at least one dominating vertex and mex$(m,H,K_{1,r})$ for every $H$ having at least two dominating vertices. |
| title | A localized approach to generalized Turán problems |
| topic | Combinatorics 05C35 |
| url | https://arxiv.org/abs/2301.05678 |