2026/07/24 by Hui Lei, Danning Wang, Yiqiao Wang
#math.CO
For an oriented graph D, let α(D) be the maximum order of an induced acyclic subdigraph, χ(D) its dichromatic number, and fas(D) the minimum number of arcs whose deletion makes D acyclic. We prove that for every fixed ζ∈ (0, 1/2), there are triangle-free graphs Gn on n vertices such that a uniformly random orientation Dn satisfies, ( (1)/(2) - ζ) e(Gn[U]) < fas(Dn[U]) ≤ (1)/(2) e(Gn[U]) with probability at least 1-exp [-Ωζ (√ n (log n)3/2)] simultaneously for every vertex set U of size at least Cζ√(nlog n). The upper bound is universal, so the feedback-arc ratio can be made arbitrarily close to the largest possible value, uniformly over all sufficiently large induced subdigraphs. In particular, α(Dn) = O(√(n log n)), and every linear-size induced subdigraph has dichromatic number Ω(√(n/log n)). This yields α(n) = Θ(√(n log n)) and t(n) = Θ(√((n)/(log n))), where α(n) and t(n) denote, respectively, the minimum of α(D) and the maximum of χ(D) over all oriented triangle-free graphs D of order n. This confirms two conjectures of Aboulker, Havet, Pirot, and Schabanel.