Directed surplus in random ℬ-free orientations
Suspected directed surplus of a random B-free orientation (Remark 1.6) · arXiv:2204.01938
Status open high confidence
No follow-up resolving Remark 1.6 was found in the published or preprint literature. The conjecture, stated informally as a remark rather than a formal conjecture in the paper, asks whether a random orientation of a B-free graph with m = ex(n, B) edges achieves directed surplus Omega(sqrt(mn)) even when the auxiliary condition ex(n, B) = Theta(n^{2-epsilon(B)}) is dropped; the main paper (published 2024 in Random Structures & Algorithms) proves the bound only under that additional density condition. A 2024 preprint (arXiv:2409.16443) on feedback arc sets in random Erdos-Renyi graphs cites the Fox-Himwich-Mani paper but does not address this specific remark.
Reviewer notes. Remark 1.6 is not labeled a conjecture in the paper — it is a brief informal remark. The main theorem (Theorem 1.5) proves beta(G) = m/2 - Omega(sqrt(mn)) for B-free orientations under the condition ex(n,B) = Theta(n^{2-epsilon(B)}); Remark 1.6 conjectures the same bound holds without that density condition. No paper specifically targeting this remark was found after five web calls. The paper was published in Random Structures & Algorithms 64.2 (2024), pp. 287-308 (doi available via Wiley).
Context
In Remark 1.6 the authors note that the proof of Theorem 1.5 uses the auxiliary condition $\mathrm{ex}(n,\mathcal{B}) = \Theta(n^{2-\varepsilon(\mathcal{B})})$ only for convenience, and that without it a random $\mathcal{B}$-free orientation is suspected to already achieve the stated directed-surplus bound.
Notes. Stated with 'we suspect' in Remark 1.6; no labelled theorem environment. PDF math is readable.
Source paper
Extremal results on feedback arc sets in digraphs
Jacob Fox, Zoe Himwich, Nitya Mani · 2022-04-19
https://arxiv.org/abs/2204.01938
PDF source