Almost all $C_k$-free oriented graphs have $Θ(n)$ backwards edges
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917352775352320 |
|---|---|
| author | Liu, Jianxi Liang, Meili |
| author_facet | Liu, Jianxi Liang, Meili |
| contents | We prove a conjecture of Kühn, Osthus, Townsend and Zhao \cite{kuhn2017structure} stating that almost every $C_k$-free oriented graph on $n$ vertices has $Θ(n)$ backwards edges in a transitive-optimal ordering. The same holds for $C_k$-free digraphs when $k$ is even. Our proof combines the hypergraph container method with a stability analysis and an inductive counting argument. As a byproduct, we also determine the typical structure of oriented graphs and digraphs that avoid the blow-up $C_{k}^t$, extending the main result of \cite{kuhn2017structure} to the blown-up setting. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_18553 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Almost all $C_k$-free oriented graphs have $Θ(n)$ backwards edges Liu, Jianxi Liang, Meili Combinatorics We prove a conjecture of Kühn, Osthus, Townsend and Zhao \cite{kuhn2017structure} stating that almost every $C_k$-free oriented graph on $n$ vertices has $Θ(n)$ backwards edges in a transitive-optimal ordering. The same holds for $C_k$-free digraphs when $k$ is even. Our proof combines the hypergraph container method with a stability analysis and an inductive counting argument. As a byproduct, we also determine the typical structure of oriented graphs and digraphs that avoid the blow-up $C_{k}^t$, extending the main result of \cite{kuhn2017structure} to the blown-up setting. |
| title | Almost all $C_k$-free oriented graphs have $Θ(n)$ backwards edges |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2603.18553 |