A bound on judicious bipartitions of directed graphs

Judicious partitioning problems on graphs ask for partitions that bound several quantities simultaneously, which have received much attention lately. Scott (2005) asked the following natural question: What is the maximum constant c(d) such that every directed graph D with m arcs and minimum outdegree d admits a bipartition V(D) = V-1 ? V-2 satisfying min{e(V-1, V-2), e(V-2, V1)} > c(d)m? Here, for i = 1, 2, e(V-i, V3-i) denotes the number of arcs in D from V-i to V3-i. Lee et al. (2016) conjectured that every directed graph D with m arcs and minimum outdegree at least d > 2 admits a bipartition V(D) = V-1 ? V-2 such that minfe(V-1; V-2); e(V-2; V-1)g > (d 1 - 2(2d 1) + o(1)) m: In this paper, we show that this conjecture holds under the additional natural condition that the minimum indegree is also at least d.