Sharp Bisection Bounds for Digraphs

Zhaoyang Ma, Shufei Wu, Qinghou Zeng

Fix an integer $d\ge 1$. We prove that, for all sufficiently large $m$, every digraph $D$ with $m$ arcs and minimum semidegree at least $d$ admits a bisection $V(D)=V_1\cup V_2$ wit…