Relative Turán densities for ordered graphs: all and nothing
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915639503880192 |
|---|---|
| author | Illingworth, Freddie Ranganathan, Arjun Versteegen, Leo Williams, Ella |
| author_facet | Illingworth, Freddie Ranganathan, Arjun Versteegen, Leo Williams, Ella |
| contents | Reiher, Rödl, Sales, and Schacht initiated the study of relative Turán densities of ordered graphs and showed that it is more subtle and interesting than the unordered case. For an ordered graph $F$, its relative Turán density, $ρ_{<}(F)$, is the greatest $α$ such that every ordered graph $G$ has an $F$-free subgraph with at least $αe(G)$ edges.
This paper contains two main results about relative Turán densities. First, we find a family of host graphs that is optimal for all $F$. Second, we characterise the ordered graphs with zero relative Turán density: precisely those with no monotone path of length two. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_21571 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Relative Turán densities for ordered graphs: all and nothing Illingworth, Freddie Ranganathan, Arjun Versteegen, Leo Williams, Ella Combinatorics 05C35 Reiher, Rödl, Sales, and Schacht initiated the study of relative Turán densities of ordered graphs and showed that it is more subtle and interesting than the unordered case. For an ordered graph $F$, its relative Turán density, $ρ_{<}(F)$, is the greatest $α$ such that every ordered graph $G$ has an $F$-free subgraph with at least $αe(G)$ edges. This paper contains two main results about relative Turán densities. First, we find a family of host graphs that is optimal for all $F$. Second, we characterise the ordered graphs with zero relative Turán density: precisely those with no monotone path of length two. |
| title | Relative Turán densities for ordered graphs: all and nothing |
| topic | Combinatorics 05C35 |
| url | https://arxiv.org/abs/2511.21571 |