2026/07/23 by Yacong Zhou
#math.CO #math.PR
Let D be an oriented graph (a digraph with no directed 2-cycles) with maximum degree Δ≥ 1, equipped with nonnegative arc weights of total weight w(D), and let fasw(D) denote the minimum weight of a feedback arc set of D. Alon (2002) proved fasw(D)≤((1)/(2)-(1)/(16√(2Δ)))w(D). We determine the optimal constant: fasw(D)≤((1)/(2)-(√(2))/(6√Δ))w(D). In fact, we show a stronger result: fasw(D)≤(1)/(2)w(D)-(√(2))/(12)∑v w2(v), where w2(v) is the ℓ2-norm of the weights of the arcs incident with v. Both bounds are attained by the unit-weight directed triangle, so the constant √(2)/6 is best possible (already among unweighted oriented graphs). The proof combines the vertex-peeling scheme of Berger and Shor with a continuous random-ordering analysis: realizing the random order by independent uniform labels renders the expected local imbalance at each vertex exactly an integrated Khintchine-type functional, and the theorem reduces to the sharp evaluation inf‖a‖2=1∫01 𝔼|∑j aj Bj(q)| dq = (√(2))/(6), where the Bj(q) are i.i.d. Bernoulli(q) random variables, which we prove via Fourier analysis. The proof also yields a randomized, near-linear-time algorithm attaining the bounds in expectation.