Optimal bisections of directed graphs

Guanwu Liu, Jie Ma, Chunlei Zu

Published 2023-02-08Version 1

In this paper, motivated by a problem of Scott and a conjecture of Lee, Loh and Sudakov we consider bisections of directed graphs. We prove that every directed graph with $m$ arcs and minimum semidegree at least $d$ admits a bisection in which at least $\left(\frac{d}{2(2d+1)}+o(1)\right)m$ arcs cross in each direction. This provides an optimal bound as well as a positive answer to a question of Hou and Wu in a stronger form.