Id: arxiv/2603.18553 Url: https://arxiv.org/abs/2603.18553 Tags: math.CO Score: 0 Title: Almost all $C_k$-free oriented graphs have $Θ(n)$ backwards edges Domain: math.CO Source: arxiv Authors: Jianxi Liu, Meili Liang Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-03-19 Page: https://delphi.science/r/arxiv/2603.18553 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.