Counting multiple graphs in generalized Turán problems
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2020
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929208957075456 |
|---|---|
| author | Gerbner, Dániel |
| author_facet | Gerbner, Dániel |
| contents | We are given graphs $H_1,\dots,H_k$ and $F$. Consider an $F$-free graph $G$ on $n$ vertices. What is the largest sum of the number of copies of $H_i$? The case $k=1$ has attracted a lot of attention.
We also consider a colored variant, where the edges of $G$ are colored with $k$ colors. What is the largest sum of the number of copies of $H_i$ in color $i$? Our motivation to study this colored variant is a recent result stating that the Turán number of the $r$-uniform Berge-$F$ hypergraphs is at most the quantity defined above for $k=2$, $H_1=K_r$ and $H_2=K_2$.
In addition to studying these new questions, we obtain new results for generalized Turán problems and also for Berge hypergraphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2007_11645 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Counting multiple graphs in generalized Turán problems Gerbner, Dániel Combinatorics We are given graphs $H_1,\dots,H_k$ and $F$. Consider an $F$-free graph $G$ on $n$ vertices. What is the largest sum of the number of copies of $H_i$? The case $k=1$ has attracted a lot of attention. We also consider a colored variant, where the edges of $G$ are colored with $k$ colors. What is the largest sum of the number of copies of $H_i$ in color $i$? Our motivation to study this colored variant is a recent result stating that the Turán number of the $r$-uniform Berge-$F$ hypergraphs is at most the quantity defined above for $k=2$, $H_1=K_r$ and $H_2=K_2$. In addition to studying these new questions, we obtain new results for generalized Turán problems and also for Berge hypergraphs. |
| title | Counting multiple graphs in generalized Turán problems |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2007.11645 |