On edge-ordered graphs with linear extremal functions
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914865854021632 |
|---|---|
| author | Kucheriya, Gaurav Tardos, Gábor |
| author_facet | Kucheriya, Gaurav Tardos, Gábor |
| contents | The systematic study of Turán-type extremal problems for edge-ordered graphs was initiated by Gerbner et al. in 2020. Here we characterize connected edge-ordered graphs with linear extremal functions and show that the extremal function of other connected edge-ordered graphs is $Ω(n\log n)$. This characterization and dichotomy are similar in spirit to results of Füredi et al. (2020) about vertex-ordered and convex geometric graphs. We also extend the study of extremal function of short edge-ordered paths by Gerbner et al. to some longer paths. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_10558 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On edge-ordered graphs with linear extremal functions Kucheriya, Gaurav Tardos, Gábor Combinatorics 05C35 The systematic study of Turán-type extremal problems for edge-ordered graphs was initiated by Gerbner et al. in 2020. Here we characterize connected edge-ordered graphs with linear extremal functions and show that the extremal function of other connected edge-ordered graphs is $Ω(n\log n)$. This characterization and dichotomy are similar in spirit to results of Füredi et al. (2020) about vertex-ordered and convex geometric graphs. We also extend the study of extremal function of short edge-ordered paths by Gerbner et al. to some longer paths. |
| title | On edge-ordered graphs with linear extremal functions |
| topic | Combinatorics 05C35 |
| url | https://arxiv.org/abs/2309.10558 |