A bound on judicious bipartitions of directed graphs

Abstract

Judicious partitioning problems on graphs ask for partitions that bound several quantities simultaneously, which have received a lot of attentions lately. Scott 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\cup V_2$ satisfying $\min \{e(V_1,V_2),e(V_2,V_1)\}\ge c_{d}m$? Here, for $i=1,2$, $e(V_i,V_{3-i})$ denotes the number of arcs in $D$ from $V_i$ to $V_{3-i}$. Lee, Loh, and Sudakov %[Judicious partitions of directed graphs, Random Struct. Alg. 48 %(2016) 147--170] conjectured that every directed graph $D$ with $m$ arcs and minimum outdegree at least $d\ge 2$ admits a bipartition $V(D)=V_1\cup V_2$ such that \[ \min\{e(V_1,V_2),e(V_2,V_1)\}\geq \Big(\frac{d-1}{2(2d-1)}+ o(1)\Big)m. \] %While it is not known whether or not the minimum outdegree condition %alone is sufficient, w We show that this conjecture holds under the additional natural condition that the minimum indegree is also at least $d$.

16 pages