Exact results on generalized Erdős-Gallai problems
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2020
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909122908127232 |
|---|---|
| author | Chakraborti, Debsoumya Chen, Da Qi |
| author_facet | Chakraborti, Debsoumya Chen, Da Qi |
| contents | Generalized Turán problems have been a central topic of study in extremal combinatorics throughout the last few decades. One such problem is maximizing the number of cliques of size $t$ in a graph of a fixed order that does not contain any path (or cycle) of length at least a given number. Both of the path-free and cycle-free extremal problems were recently considered and asymptotically solved by Luo. We fully resolve these problems by characterizing all possible extremal graphs. We further extend these results by solving the edge-variant of these problems where the number of edges is fixed instead of the number of vertices. We similarly obtain exact characterization of the extremal graphs for these edge variants. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2006_04681 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Exact results on generalized Erdős-Gallai problems Chakraborti, Debsoumya Chen, Da Qi Combinatorics Generalized Turán problems have been a central topic of study in extremal combinatorics throughout the last few decades. One such problem is maximizing the number of cliques of size $t$ in a graph of a fixed order that does not contain any path (or cycle) of length at least a given number. Both of the path-free and cycle-free extremal problems were recently considered and asymptotically solved by Luo. We fully resolve these problems by characterizing all possible extremal graphs. We further extend these results by solving the edge-variant of these problems where the number of edges is fixed instead of the number of vertices. We similarly obtain exact characterization of the extremal graphs for these edge variants. |
| title | Exact results on generalized Erdős-Gallai problems |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2006.04681 |