On non-degenerate Turán problems for expansions
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913728975339520 |
|---|---|
| author | Gerbner, Dániel |
| author_facet | Gerbner, Dániel |
| contents | The $r$-uniform expansion $F^{(r)+}$ of a graph $F$ is obtained by enlarging each edge with $r-2$ new vertices such that altogether we use $(r-2)|E(F)|$ new vertices. Two simple lower bounds on the largest number $\mathrm{ex}_r(n,F^{(r)+})$ of $r$-edges in $F^{(r)+}$-free $r$-graphs are $Ω(n^{r-1})$ (in the case $F$ is not a star) and $\mathrm{ex}(n,K_r,F)$, which is the largest number of $r$-cliques in $n$-vertex $F$-free graphs. We prove that $\mathrm{ex}_r(n,F^{(r)+})=\mathrm{ex}(n,K_r,F)+O(n^{r-1})$. The proof comes with a structure theorem that we use to determine $\ex_r(n,F^{(r)+})$ exactly for some graphs $F$, every $rχ(F)$ and sufficiently large $n$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_01857 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On non-degenerate Turán problems for expansions Gerbner, Dániel Combinatorics The $r$-uniform expansion $F^{(r)+}$ of a graph $F$ is obtained by enlarging each edge with $r-2$ new vertices such that altogether we use $(r-2)|E(F)|$ new vertices. Two simple lower bounds on the largest number $\mathrm{ex}_r(n,F^{(r)+})$ of $r$-edges in $F^{(r)+}$-free $r$-graphs are $Ω(n^{r-1})$ (in the case $F$ is not a star) and $\mathrm{ex}(n,K_r,F)$, which is the largest number of $r$-cliques in $n$-vertex $F$-free graphs. We prove that $\mathrm{ex}_r(n,F^{(r)+})=\mathrm{ex}(n,K_r,F)+O(n^{r-1})$. The proof comes with a structure theorem that we use to determine $\ex_r(n,F^{(r)+})$ exactly for some graphs $F$, every $rχ(F)$ and sufficiently large $n$. |
| title | On non-degenerate Turán problems for expansions |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2309.01857 |