{"id":"arxiv/2607.22044","url":"https://arxiv.org/abs/2607.22044","tags":["math.CO"],"score":0,"title":"Feedback-arc robustness in random orientations of pseudorandom triangle-free graphs","domain":"math.CO","source":"arxiv","authors":["Hui Lei","Danning Wang","Yiqiao Wang"],"reviews":0,"subject":"math.CO","summary":"For an oriented graph $D$, let $\\vecα(D)$ be the maximum order of an induced acyclic subdigraph, $\\vecχ(D)$ its dichromatic number, and $\\mathrm{fas}(D)$ the minimum number of arcs whose deletion makes $D$ acyclic. We prove that for every fixed $ζ\\in (0, 1/2)$, there are triangle-free graphs $G_n$ on $n$ vertices such that a uniformly random orientation $D_n$ satisfies, $$ \\left( \\frac{1}{2} - ζ\\right) e(G_n[U]) < \\mathrm{fas}(D_n[U]) \\leq \\frac{1}{2} e(G_n[U]) $$ with probability at least $1-\\exp\\!\\left[-Ω_ζ\\!\\left(\\sqrt n\\,(\\log n)^{3/2}\\right)\\right]$ simultaneously for every vertex set…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-24","reactions":{}}