Feedback-arc robustness in random orientations of pseudorandom triangle-free graphs

Abstract

For an oriented graph $D$, let $\vec{\hat{I}}\pm (D)$ be the maximum order of an induced acyclic subdigraph, $\vec{\ddot{I}}‡(D)$ its dichromatic number, and $\mathrm{fas}(D)$ the minimum number of arcs whose deletion makes $D$ acyclic. We prove that for every fixed $\hat{I}\P \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}-\hat{I}\P \right)e(G_n[U])<\mathrm{fas}(D_n[U])\le \frac{1}{2}e(G_n[U])$$ with probability at least $1-\exp \left[-\hat{I}{\text{c◯}}_{\hat{I}}\P \left(\sqrt{n}(\log n{)}^{3/2}\right)\right]$ simultaneously for every vertex set $U$ of size at least $C_{\hat{I}}\P \sqrt{n\log 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, $\vec{\hat{I}}\pm (D_n)=O(\sqrt{n\log n})$, and every linear-size induced subdigraph has dichromatic number $\hat{I}\text{c◯}(\sqrt{n/\log n})$. This yields $\vec{\hat{I}}\pm (n)=\hat{I}˜(\sqrt{n\log n})$ and $\vec{t}(n)=\hat{I}˜\left(\sqrt{\frac{n}{\log n}}\right)$, where $\vec{\hat{I}}\pm (n)$ and $\vec{t}(n)$ denote, respectively, the minimum of $\vec{\hat{I}}\pm (D)$ and the maximum of $\vec{\ddot{I}}‡(D)$ over all oriented triangle-free graphs $D$ of order $n$. This confirms two conjectures of Aboulker, Havet, Pirot, and Schabanel.