# Optimal bisections of directed graphs

Guanwu Liu Jie Ma Chunlei Zu

###### Abstract

In this paper, motivated by a problem of Scott [33] and a conjecture of Lee,
Loh and Sudakov [26] 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 [20] in a stronger form.

††footnotetext: School of Mathematical Sciences, University of Science and
Technology of China, Hefei, Anhui 230026, China. Research supported by the
National Key R and D Program of China 2020YFA0713100, National Natural Science
Foundation of China grant 12125106, and Anhui Initiative in Quantum
Information Technologies grant AHY150200.

##  1 Introduction

As one of the most fundamental problems in the common field of combinatorics
and theoretical computer science, graph partitioning problems have been
studied extensively in the literature. A well-known example is the Max-Cut
problem, which asks to find a vertex-partition $V_{1}\cup V_{2}$ of a given
graph with $m$ edges that maximizes the number of edges between $V_{1}$ and
$V_{2}$. A uniformly random partition shows that this number is at least
$m/2$. This bound was improved to $m/2+(\sqrt{2m+1/4}-1/2)/4$ by a prominent
result of Edwards [11, 12] which is optimal for infinitely many graphs (see
Alon [2] for more advances).

In past decades, a new area of judicious partitioning problems has arisen,
where the common theme seeks for partitions optimizing several quantities
simultaneously. A celebrated result in this area is due to Bollobás and Scott
[7], who showed that any graph with $m$ edges admits a bipartition $V_{1}\cup
V_{2}$ of its vertex set such that the number of edges between $V_{1}$ and
$V_{2}$ is at least $m/2+(\sqrt{2m+1/4}-1/2)/4$ (i.e., Edwards’ bound) and
moreover for each $i\in\\{1,2\\}$, the number of edges contained in $V_{i}$ is
at most $m/4+(\sqrt{2m+1/4}-1/2)/8$. There has been a large body of research
for judicious partitioning problems (see, e.g., [3, 8, 10, 13, 15, 16, 22, 24,
25, 26, 29, 30, 31, 32, 34, 36, 37]). For a systematic treatment on related
problems and results, we refer interested readers to the surveys [9, 33, 35].

In this paper, we study partitioning problems for directed graphs (i.e.,
digraphs). For a digraph $D$ and a bipartition $V(D)=V_{1}\cup V_{2}$, let
$e(V_{1},V_{2})$ denote the size of the directed cut $(V_{1},V_{2})$, i.e.,
the number of arcs in $D$ directed from $V_{1}$ to $V_{2}$. It is easy to find
a directed cut of size at least $m/4$ in any digraph with $m$ edges; on the
other hand, Alon, Bollobás, Gyárfás, Lehel and Scott [4] constructed digraphs
whose maximum directed cut is $m/4+O(m^{4/5})$. A natural problem in the
judicious setting would be to find a bipartition $V(D)=V_{1}\cup V_{2}$ that
maximizes $\min\\{e(V_{1},V_{2}),e(V_{2},V_{1})\\}$. However, if the digraph
$D$ is an oriented star where all arcs are oriented from its center in one
direction, then one of $e(V_{1},V_{2})$ and $e(V_{2},V_{1})$ will always be
zero for any bipartition $V_{1}\cup V_{2}$. To avoid this situation, Scott
[33] suggested the following problem by imposing a minimum degree condition.

######  Problem 1.1 (Scott [33], see Problem 3.27).

Let $d$ be a positive integer. What is the largest constant $c_{d}$ such that
every digraph $D$ with $m$ arcs and minimum outdegree $d$ admits a bipartition
$V(D)=V_{1}\cup V_{2}$ such that

$\min\left\\{e(V_{1},V_{2}),e(V_{2},V_{1})\right\\}\geq c_{d}\cdot m?$

It is easy to obtain $c_{1}=0$. Lee, Loh and Sudakov [26] proved that
$c_{2}=1/6+o(1)$ and $c_{3}=1/5+o(1)$. For the general case, they made the
following attractive conjecture.

######  Conjecture 1.2 (Lee, Loh and Sudakov [26], see Conjecture 1.2).

Let $d\geq 3$ be a positive integer. Every digraph $D$ with $m$ arcs and
minimum outdegree at least $d+1$ admits a bipartition $V(D)=V_{1}\cup V_{2}$
such that

$\displaystyle\min\left\\{e(V_{1},V_{2}),e(V_{2},V_{1})\right\\}\geq\left(\frac{d}{2(2d+1)}+o(1)\right)m.$
(1.1)

If it is true, this would provide the optimal bound and thus show
$c_{d+1}=\frac{d}{2(2d+1)}+o(1)$ for Problem 1.1 (see the construction below).
Recently, Liu and Yu [28] proved the next case of Conjecture 1.2, i.e., for
digraphs with minimum outdegree at least 4. It is not clear if the minimum
outdegree alone is sufficient for Conjecture 1.2 for large $d$ and there have
been researches for partitioning digraphs under additional conditions. A
natural additional assumption here is to impose some minimum indegree. In this
line, Hou, Ma, Yu and Zhang [19] proved Conjecture 1.2 under the additional
assumption that the minimum indegree is at least $d+1$. In other words, the
authors of [19] proved that (1.1) holds for digraphs with minimum semidegree
at least $d+1$. In [20], Hou and Wu proposed the following question for a
weaker minimum semidgree condition (also see Conjecture 4.6 in [35]).

######  Question 1.3 (Hou and Wu [20]).

Is it true that for every positive integer $d$, every digraph $D$ with $m$
arcs and minimum semidegree $d$ admits a bipartition $V(D)=V_{1}\cup V_{2}$
such that

$\min\left\\{e(V_{1},V_{2}),e(V_{2},V_{1})\right\\}\geq\left(\frac{d}{2(2d+1)}+o(1)\right)m?$

In the same paper [20], Hou and Wu proved that the above conclusion holds for
all oriented graphs with minimum semidegree $d\geq 21$. Their proofs are
involved and work only for oriented graphs. Later, Hou, Li and Wu [18] gave a
positive answer to Question 1.3 for $d\leq 3$.

A _bisection_ of a (di)graph is a bipartition of its vertex set in which the
number of vertices in the two parts differ by at most 1. Finding bisections is
of particular interest in partitioning problems (see, e.g., [14, 21, 23, 25,
27, 37]) and it is usually more challenging.

Here we give an affirmative answer to Question 1.3 in a stronger form, where
we show that the desired bipartition can be further chosen as a bisection.

######  Theorem 1.4.

Let $d$ be a positive integer. Every digraph $D$ with $m$ arcs and minimum
semidegree at least $d$ admits a bisection $V(D)=V_{1}\cup V_{2}$ such that

$\min\left\\{e(V_{1},V_{2}),e(V_{2},V_{1})\right\\}\geq\left(\frac{d}{2(2d+1)}+o(1)\right)m.$

The proof of Theorem 1.4 at the basic level follows by an approach launched by
Bollobás and Scott [6, 9] and further developed in the subsequent works such
as [20, 25, 26, 30]. It is to first partition the set $X$ of vertices with
large degree by some optimization and then partition the set $Y$ of the
remaining vertices using some randomize process which is carefully designed
based on the structures of the cut $(X,Y)$ as well as the subgraph induced by
$Y$. Then using probabilistic concentration inequalities, one can bound the
deviations of random performances in terms of parameters associated with the
aforementioned structures (see Lemma 2.7 for implementing this step in our
proof). For partitioning digraphs, the difficulties are often to untangle the
intricate relationships between these parameters. The new ingredients at the
core of our proof are some relatively neat estimations on the arcs between $X$
and $Y$ in each direction (we refer to Subsection 3.3 for more details).

Finally we remark that the bounds in Conjecture 1.2 and Question 1.3 are
asymptotically optimal by considering the following digraphs given by Lee, Loh
and Sudakov [26]: Take $k$ disjoint copies of $K_{2d+1}$ oriented along an
Eulerian circuit, and a single copy of $K_{2d+3}$ oriented in a similar manner
which is disjoint from the copies of $K_{2d+1}$; then fix a vertex $v_{0}$ of
$K_{2d+3}$, and add arcs from all the vertices in the copies of $K_{2d+1}$ to
$v_{0}$. Clearly, the resulting digraph $D$ has minimum outdegree $d+1$ and
minimum semidegree $d$, whose number of arcs equals

$\displaystyle m=\;kd(2d+1)+(d+1)(2d+3)+k(2d+1)=\;k(d+1)(2d+1)+(d+1)(2d+3).$

For any bipartition of $K_{2d+1}$ oriented along an Eulerian circuit, the
number of arcs in any direction is at most $\frac{d(d+1)}{2}$. Then for every
bipartition $V(D)=V_{1}\cup V_{2}$ (say $v_{0}\in V_{1}$), we have

$e(V_{1},V_{2})\leq
k\frac{d(d+1)}{2}+\frac{(d+1)(d+2)}{2}=\frac{d}{2(2d+1)}m+\frac{(d+1)^{2}}{2d+1}.$

Hence we can conclude that

$\max_{V(D)=V_{1}\cup
V_{2}}\min\left\\{e(V_{1},V_{2}),e(V_{2},V_{1})\right\\}\leq\left(\frac{d}{2(2d+1)}+o(1)\right)m.$

The rest of this paper is organized as follows. In Section 2, we give
notations and collect lemmas for the coming proof. In Section 3, we complete
the proof of Theorem 1.4. Finally in Section 4, we offer some concluding
remarks.

##  2 Preliminaries

###  2.1 Notations

We use standard notations in graph theory. All digraphs considered in this
paper are finite with no loops and no multiple arcs (but a pair of arcs in
opposite directions is allowed). For a digraph $D$, we denote by $V(D)$ the
vertex set of $D$ and by $A(D)$ the arc set of $D$. Let $x,y$ be two vertices
in $D$. We write $xy$ or $x\to y$ for an arc in $D$ with head $x$ and tail
$y$. We write $N_{D}^{+}(x)=\\{y:xy\in A(D)\\}$ and $N_{D}^{-}(x)=\\{y:yx\in
A(D)\\}$, and call $d_{D}^{+}(x):=|N_{D}^{+}(x)|$ and
$d_{D}^{-}(x):=|N_{D}^{-}(x)|$ as the outdegree and indegree of $x$ in $D$,
respectively. The degree of $x$ in $D$ is defined as
$d_{D}(x)=d^{+}_{D}(x)+d^{-}_{D}(x)$, and the semidegree of $x$ in $D$ is
$\min\\{d^{+}_{D}(x),d^{-}_{D}(x)\\}$. We will omit the subscripts in the
above definitions when this is not ambiguous.

The maximum degree $\Delta(D)$ of $D$ is $\max\\{d_{D}(x):x\in V(D)\\}$. The
minimum outdegree of $D$ is $\delta^{+}(D)=\min\\{d_{D}^{+}(x):x\in V(D)\\}$
and the minimum indegree of $D$ is $\delta^{-}(D)=\min\\{d_{D}^{-}(x):x\in
V(D)\\}$. Finally, we define the minimum semidegree of $D$ to be
$\delta^{0}(D)=\min\\{\delta^{+}(D),\delta^{-}(D)\\}$.

For any $X\subseteq V(D)$, the subgraph of $D$ induced by $X$ is denoted by
$D[X]$. We write $e(X)$ to express the number of arcs contained in $D[X]$. For
disjoint sets $X,Y\subseteq V(D)$, by $(X,Y)$ we denote the set of all arcs in
$D$ with head in $X$ and tail in $Y$. Let $e(X,Y)$ be the number of arcs in
$(X,Y)$. Throughout the rest of the paper, we write $[k]$ for the set of
integers $\\{1,2,\ldots,k\\}$ where $k$ denotes a positive integer.

###  2.2 Previous lemmas

In this subsection, we collect some previous lemmas for the use of the coming
proof. First we state the following version of the Azuma-Hoeffding inequality.

######  Lemma 2.1 (Azuma [5], Hoeffding [17]).

Let $Z_{1},\ldots,Z_{n}$ be independent random variables taking values in
$\\{1,\ldots,k\\}$, let $Z:=(Z_{1},\ldots,Z_{n})$, and let
$f:\\{1,\ldots,k\\}^{n}\rightarrow\mathbb{N}$ such that
$|f(Y)-f(Y^{\prime})|\leq c_{i}$ for any $Y,Y^{\prime}\in\\{1,\ldots,k\\}^{n}$
which differ only in the i-th coordinate. Then for any $z>0$,

$\mathbb{P}(f(Z)\geq\mathbb{E}(f(Z))+z)\;\leq\;exp\left(\frac{-z^{2}}{2\sum_{i=1}^{n}c_{i}^{2}}\right),$
$\mathbb{P}(f(Z)\leq\mathbb{E}(f(Z))-z)\;\leq\;exp\left(\frac{-z^{2}}{2\sum_{i=1}^{n}c_{i}^{2}}\right).$

A natural, basic idea for finding good cuts is to investigate cuts generated
by random partitions. If we place each vertex of a digraph $D$ to a side
uniformly and independently, then we get a random partition with the expected
number of arcs in each direction being $e(D)/4$. In the following lemma, Lee,
Loh and Sudakov [26] showed that such a partition (with asymptotically optimal
performances) can be realized under some additional restrictions.

######  Lemma 2.2 (Lee, Loh and Sudakov [26]).

Let $D$ be a digraph with $n$ vertices and $m$ arcs. For every
$\varepsilon>0$, if $m\geq 8n/\varepsilon^{2}$ or
$\Delta(D)\leq\varepsilon^{2}m/4$, then $D$ admits a bipartition
$V(D)=V_{1}\cup V_{2}$ such that

$\min\\{e(V_{1},V_{2}),e(V_{2},V_{1})\\}\geq\frac{1}{4}m-\varepsilon m.$

This lemma was extended by Hou, Wu and Yan [23] in the following bisection
version.

######  Lemma 2.3 (Hou, Wu and Yan [23]).

Let $D$ be a digraph with $n$ vertices and $m$ arcs. For every
$\varepsilon>0$, if $m\geq 16n/\varepsilon^{2}$ or $\Delta(D)\leq$
$\varepsilon^{2}m/8$, then $D$ admits a bisection $V(D)=V_{1}\cup V_{2}$ such
that

$\min\\{e(V_{1},V_{2}),e(V_{2},V_{1})\\}\geq\frac{1}{4}m-\varepsilon m.$

We now define an important structural concept in this study introduced by Lee,
Loh and Sudakov [25]. Let $T$ be a connected component of a given (undirected)
graph $G$. We say that $T$ is a tight component of $G$ if it satisfies the
following properties:

  * (i)

for every vertex $v\in V(T)$, $T-v$ contains a perfect matching, and

  * (ii)

for every vertex $v\in V(T)$ and every perfect matching $M$ of $T-v$, no edge
in $M$ has exactly one end adjacent to $v$.

Clearly a tight component must have an odd number of vertices. The underlying
graph $G_{D}$ of a digraph $D$ is a simple graph obtained from $D$ by ignoring
arc orientations and removing redundant multi-edges. We say a component of $D$
is tight if the corresponding component of $G_{D}$ is tight, and essential if
it is tight and does not contain two arcs in opposite directions.

Let $\\{e_{1},\ldots,e_{s}\\}$ be a maximum matching in a graph $G$, and let
$W$ be the set of vertices not in the matching. Let $v\in V(e_{i})$ and $w\in
W$. With respect to this fixed matching, $v$ is called a free neighbor of $w$
if $w$ is adjacent to $v$ but not adjacent to the other endpoint of $e_{i}$.
We call $w\in W$ a free vertex if it has at least one free neighbor in the
matching, and a non-free vertex otherwise. In [26] Lee, Loh and Sudakov showed
that there is a bijective correspondence between non-free vertices and tight
components under certain conditions.

######  Lemma 2.4 (Lee, Loh and Sudakov [26]).

Let $e_{1},\ldots,e_{s}$ be the edges of a maximum matching in an undirected
graph $G$, and let $W$ be the set of vertices not in the matching. Further
assume that among all matchings of maximum size, we have chosen one which
maximizes the number of free vertices in $W$. Then, every tight component
contains a distinct non-free vertex of $W$, and all non-free vertices of $W$
are covered in this way (i.e., there is a bijective correspondence).

Using this lemma, the authors of [26] (see its Lemma 3.2) managed to decompose
an undirected graph into induced stars plus an independent set. We need the
following version of this decomposition result which can be easily deduced
from the original proof of [26].111In the original statement of Lemma 3.2 in
[26], $G$ is a graph with $n$ vertices and $m\leq Cn$ edges and $A$ denotes
the set of vertices with degree at least $2C/\varepsilon$, where $\varepsilon$
and $C$ are arbitrary positive reals. In particular $|A|\leq\varepsilon n$.

######  Lemma 2.5 (Lee, Loh and Sudakov [26], Lemma 3.2).

Let $G$ be an undirected graph with $\tau$ tight components. Let $A$ be a
subset of $V(G)$. Let $e_{1},\ldots,e_{s}$ be the edges of a maximum matching
in $G$ such that among all matchings of maximum size, we have chosen one which
maximizes the number of free vertices. Then there exists a partition
$V(G)=T_{1}\cup T_{2}\cup\cdots\cup T_{s}\cup U$ such that

  * $(i)$

each $T_{i}$ induces a star containing the edge $e_{i}$ in the maximum
matching,

  * $(ii)$

at most one leaf vertex in each $T_{i}$ is contained in $A$, and

  * $(iii)$

$U$ is an independent set of order $|U|\leq\tau+|A|$.

The following lemma of [26] and its variances serve as a guiding tool in the
recent development of digraph partitioning problems (see, i.e., [26, 23, 18]).

######  Lemma 2.6 (Lee, Loh and Sudakov [26]).

For any positive constants $C$ and $\varepsilon$, there exist $\gamma$,
$n_{0}>0$ for which the following holds. Let $D$ be a digraph with $n\geq
n_{0}$ vertices and at most $Cn$ arcs. Suppose $X\subseteq V(D)$ is a set of
at most $\gamma n$ vertices and $X_{1},X_{2}$ is a partition of $X$. Let
$Y=V(D)\setminus X$ and let $\tau$ be the number of components with odd order
in $D[Y]$. If every vertex in $Y$ has degree at most $\gamma n$ in $D$, then
there is a bipartition $V(D)=V_{1}\cup V_{2}$ with $X_{i}\subseteq V_{i}$ for
$i=1,2$ such that

$e(V_{1},V_{2})\geq
e(X_{1},X_{2})+\frac{e(X_{1},Y)+e(Y,X_{2})}{2}+\frac{e(Y)}{4}+\frac{n-\tau}{8}-\varepsilon
n,$ $e(V_{2},V_{1})\geq
e(X_{2},X_{1})+\frac{e(X_{2},Y)+e(Y,X_{1})}{2}+\frac{e(Y)}{4}+\frac{n-\tau}{8}-\varepsilon
n.$

We mention that Hou, Wu and Yan [23] extended this lemma by replacing $\tau$
with the number of tight components in $D[Y]$ and requiring the bipartition
$V(D)=V_{1}\cup V_{2}$ to be a bisection, and more recently, Hou, Li and Wu
[18] improved it by showing $\tau$ can be chosen as the number of essential
components in $D[Y]$. To show the desired bisection of Theorem 1.4, we will
need a further strengthening of Lemma 2.6 for which we prove in the following
subsection.

###  2.3 A strengthening of Lemma 2.6

In this subsection, using probabilistic arguments we prove Lemma 2.7, which
generalizes Lemma 2.6 as well as its variances mentioned above. This lemma
will allow us to extend a pre-optimized partition of the set of vertices with
large degree to a ‘good’ bisection of the entire digraph. We like to point out
that it is crucial for the proof in Section 3 to use $\tau$ as the number of
essential components.

Since the proof is similar to that of Lemma 3.1 in [26] and Lemma 3.5 in [23],
we shall only give detailed explanations for steps which reflect the
difference and sketch the rest of them.

######  Lemma 2.7.

For any positive constants $C$ and $\varepsilon$, there exist $\gamma$,
$n_{0}>0$ for which the following holds. Let $D$ be a digraph with $n\geq
n_{0}$ vertices and at most $Cn$ arcs. Suppose $X\subseteq V(D)$ is a set of
at most $\gamma n$ vertices and $X_{1},X_{2}$ is a partition of $X$. Let
$Y=V(D)\setminus X$ and let $\tau$ be the number of essential components in
$D[Y]$. If every vertex in $Y$ has degree at most $\gamma n$ in $D$, then
there is a bisection $V(D)=V_{1}\cup V_{2}$ with $X_{i}\subseteq V_{i}$ for
$i=1,2$ such that

$e(V_{1},V_{2})\geq
e(X_{1},X_{2})+\frac{e(X_{1},Y)+e(Y,X_{2})}{2}+\frac{e(Y)}{4}+\frac{n-\tau}{8}-\varepsilon
n,$ $e(V_{2},V_{1})\geq
e(X_{2},X_{1})+\frac{e(X_{2},Y)+e(Y,X_{1})}{2}+\frac{e(Y)}{4}+\frac{n-\tau}{8}-\varepsilon
n.$

###### Proof.

Let $G$ be the underlying graph of $D$. Let $\tau^{*}$ be the number of tight
components in $G[Y]$, and let $\sigma$ be the number of tight components in
$G[Y]$ which contains an antiparallel pair when lifted to $D$. Clearly,
$\tau=\tau^{*}-\sigma$ is the number of essential components in $D[Y]$.

We choose $e_{1},\ldots,e_{s}$ to be the edges of a maximum matching in $G$
such that

  * (1).

among all matchings of maximum size, we choose one which maximizes the number
of free vertices in the set $W$ of vertices not in the matching, and

  * (2).

subject to the above, we require that the number of edges $e_{i}$ which
corresponds to a pair of arcs in opposite directions when lifted to $D$ (call
$e_{i}$ special) is maximized.

We claim that the number of special edges in $\\{e_{1},\ldots,e_{s}\\}$ is at
least $\sigma$. It suffices to show that each tight component $B$ in $G[Y]$
which contains an antiparallel pair when lifted to $D$ contributes at least
one special edge. Suppose that $B$ has $2k+1$ vertices and $D[B]$ contains
$u\to v$ and $v\to u$. It is easy to see that any maximum matching in $G$
contains $k$ edges in $B$ and for any matching of $k$ edges in $B$, the
remaining vertex of $B$ is a non-free vertex. So taking any matching of $k$
edges in $B$ will not affect the property $(1)$. Now we just need to show that
there exists a matching of $k$ edges in $B$ containing the edge $uv$, which
can be obtained from any perfect matching $M$ of $B-v$ by replacing the edge
of $M$ containing $u$ with the edge $uv$.

Let $A=\\{x\in V(G):d_{G}(x)\geq 2C/\varepsilon\\}$. Since $e(G)\leq e(D)\leq
Cn$, we have $|A|\leq\varepsilon n$. Applying Lemma 2.5 to $G[Y]$ with respect
to $A$ and $\\{e_{1},\ldots,e_{s}\\}$, we obtain a partition
$Y=T_{1}\cup\cdots\cup T_{s}\cup U$ such that each $T_{i}$ induces a star
containing the edge $e_{i}$, at most one leaf vertex in each $G[T_{i}]$ has
degree at least $2C/\varepsilon$ in the whole graph $G$, and $U$ is an
independent set with $|U|\leq\tau^{*}+\varepsilon n$.

We then randomly construct a partition $V(D)=V_{1}\cup V_{2}$ as follows:
place each $X_{i}$ in $V_{i}$ for $i=1,2$; partition each $T_{i}$ by
independently placing its center vertex $v_{i}$ on a uniformly random side,
and then placing the rest of $T_{i}\backslash\\{v_{i}\\}$ on the other side;
place each remaining vertex (from the set $U$) on a uniformly random side.

Define random variables $Y_{1}=e(V_{1},V_{2})$ and $Y_{2}=e(V_{2},V_{1})$. For
an arc $e=u\to v$, let $I_{e}$ be the indicator random variable of the event
that $u\in V_{1}$ and $v\in V_{2}$. Then $Y_{1}=\sum_{e\in A(D)}I_{e}$. We see
that $\mathbb{E}[I_{e}]=1$ if $u\in X_{1}$ and $v\in X_{2}$ and
$\mathbb{E}[I_{e}]=1/2$ if either $u\in X_{1}$ and $v\in Y$, or $u\in Y$ and
$v\in X_{2}$. For an arc $e$ in $D[Y]$, if $e$ is an arc induced by some set
$T_{i}$, then $\mathbb{E}[I_{e}]=1/2$; otherwise, $\mathbb{E}[I_{e}]=1/4$.
Note that any special edge $e_{i}$ contributes two arcs induced by $T_{i}$, so
the total number of arcs induced by the sets $T_{i}$ is at least
$\frac{|Y|-|U|}{2}+\sigma\geq\frac{(n-\gamma n)-(\tau^{*}+\varepsilon
n)}{2}+\sigma$. Therefore, as $\tau=\tau^{*}-\sigma$, we have

$\displaystyle\mathbb{E}[Y_{1}]\geq\;$ $\displaystyle
e(X_{1},X_{2})+\frac{e(X_{1},Y)+e(Y,X_{2})}{2}+\frac{e(Y)}{4}+\frac{1}{4}\left[\frac{(n-\gamma
n)-(\tau^{*}+\varepsilon n)}{2}+\sigma\right]$ $\displaystyle\geq\;$
$\displaystyle
e(X_{1},X_{2})+\frac{e(X_{1},Y)+e(Y,X_{2})}{2}+\frac{e(Y)}{4}+\frac{n-\tau}{8}-\frac{(\varepsilon+\gamma)n}{8},$

where we choose $\gamma\ll\varepsilon,C$. Similarly, we can derive that

$\mathbb{E}[Y_{2}]\geq
e(X_{2},X_{1})+\frac{e(X_{2},Y)+e(Y,X_{1})}{2}+\frac{e(Y)}{4}+\frac{n-\tau}{8}-\frac{(\varepsilon+\gamma)n}{8}.$

Now we have reached the same position as in Lemma 3.1 of [26] and Lemma 3.5 of
[23]. Following the same arguments therein, one can use Lemma 2.1 (the Azuma-
Hoeffding inequality) to control the deviations of random variables
$Y_{1},Y_{2},|V_{1}|,|V_{2}|$ of the randomized partition $V_{1}\cup V_{2}$.
This leads to an almost bisection $V_{1}\cup V_{2}$ with desired bounds on
$e(V_{1},V_{2})$ and $e(V_{2},V_{1})$, where
$|V_{i}-n/2|=o_{\varepsilon,C}(n)+\gamma n$. Since $e(D)\leq Cn$, the number
of vertices with degree at most $4C$ is at least $n/2$. As shown in [23], one
can equalize $|V_{1}|$ and $|V_{2}|$ by moving around
$o_{\varepsilon,C}(n)+\gamma n$ vertices with degree at most $4C$, which will
only affect $e(V_{1},V_{2})$ and $e(V_{2},V_{1})$ by at most $\varepsilon n/2$
(as $\gamma\ll\varepsilon,C$). This completes the proof of Lemma 2.7. ∎

##  3 Proof of Theorem 1.4

Let $d$ be a positive integer and let $D$ be a digraph with $n$ vertices and
$m$ arcs whose minimum semidegree is at least $d$. Let $\varepsilon$ be any
positive real number and $m$ be sufficiently large compared with
$d,\varepsilon$. Our goal is to find a bisection $V(D)=V_{1}\cup V_{2}$ such
that

$\min\\{e(V_{1},V_{2}),e(V_{2},V_{1})\\}\geq\left(\frac{d}{2(2d+1)}-\varepsilon\right)m.$
(3.1)

As $n(n-1)\geq m$, we may also assume that $n$ is sufficiently large compared
with $d,\varepsilon$ (so that Lemma 2.7 can be applied later). If $m\geq
256(2d+1)^{2}n$, then applying Lemma 2.3 with $\varepsilon=\frac{1}{4(2d+1)}$
yields a bisection $V(D)=V_{1}\cup V_{2}$ such that

$\min\\{e(V_{1},V_{2}),e(V_{2},V_{1})\\}\;\geq\;\frac{m}{4}-\frac{m}{4(2d+1)}=\frac{d}{2(2d+1)}m,$

as desired. So in the rest of the proof we may assume that (also as the
minimum outdegree is at least $d$)

$dn\leq m<256(2d+1)^{2}n.$ (3.2)

###  3.1 The initial partition $V(D)=X\cup Y$

Throughout the rest of the proof, we consider the partition $V(D)=X\cup Y$
such that $X:=\\{v\in V(D):d_{D}(v)\geq n^{3/4}\\}$ and $Y:=V(D)\setminus X$.
Then, by (3.2),

$|X|\cdot n^{3/4}\leq\sum_{v\in X}d_{D}(v)\;\leq\sum_{v\in
V(D)}d_{D}(v)=2m<512(2d+1)^{2}n.$

Hence, $|X|=O(m/n^{3/4})=O(n^{1/4})$, and thus

$e(X)\leq|X|^{2}=O(n^{1/2})=O(m^{1/2}).$

We emphasize that in the following proof, we will only use the semidegree
condition for vertices in $Y$. For the sake of simplicity we remove all arcs
within $X$, and update $m$ to be the new total number of arcs in the resulting
digraph.222Note that this will not change the indegree and outdegree of each
vertex in $Y$. Therefore from now on, we may assume that

$\displaystyle e(X)=0.$

Note that this will only affect $O(m^{1/2})$ amount of arcs. So to prove
(3.1), it suffices to show that the resulting digraph (which we still call
$D$) has a bisection $V(D)=V_{1}\cup V_{2}$ for which

$\min\\{e(V_{1},V_{2}),e(V_{2},V_{1})\\}\geq\Big{(}\frac{d}{2(2d+1)}-\frac{\varepsilon}{2}\Big{)}m.$
(3.3)

We will first find a good bipartition for the set of vertices of large degree
$X$ and we begin by introducing some useful concepts. As we shall see later,
the vertices in $X$ whose outdegree and indegree differ significantly play
important roles. For $v\in X$, we define

$s^{+}(v):=d^{+}(v)-d^{-}(v),~{}~{}s^{-}(v):=d^{-}(v)-d^{+}(v),~{}\mbox{ and
}~{}s(v):=|d^{+}(v)-d^{-}(v)|.$

For a partition $X=X_{1}\cup X_{2}$, its ordered gap is defined as

$\theta(X_{1},X_{2})=\Big{(}e(X_{1},Y)+e(Y,X_{2})\Big{)}-\Big{(}e(X_{2},Y)+e(Y,X_{1})\Big{)}.$

Since $e(X)=0$, we also see that

$\displaystyle\theta(X_{1},X_{2})=\sum_{v\in X_{1}}s^{+}(x)-\sum_{v\in
X_{2}}s^{+}(x).$ (3.4)

For a given partition $X=X_{1}\cup X_{2}$, we say a vertex $v\in X$ is forward
if either $v\in X_{1}$ and $s^{+}(v)>0$, or $v\in X_{2}$ and $s^{-}(v)>0$;
otherwise, we say $v$ is backward. Let $X_{f}:=\\{v\in X:v\mbox{ is
forward}\\}$ and $X_{b}:=\\{v\in X:v\mbox{ is backward}\\}$. Then we can
rewrite (3.4) as the following

$\theta(X_{1},X_{2})=\sum_{v\in X_{f}}s(x)-\sum_{v\in X_{b}}s(x).$ (3.5)

###  3.2 Partitioning $X$

In the rest of this section, we choose the partition $X=X_{1}\cup X_{2}$ such
that $|\theta(X_{1},X_{2})|$ is minimum. Note that
$\theta(X_{1},X_{2})=-\theta(X_{2},X_{1})$. So by swapping $X_{1}$ and $X_{2}$
if necessary, we may assume $\theta(X_{1},X_{2})\geq 0$. In the following, we
write $\theta=\theta(X_{1},X_{2})$, unless otherwise specified.

Let $\tau$ be the number of essential components in $D[Y]$. Note that $n$ is
sufficiently large compared with $d,\varepsilon$. So applying Lemma 2.7 with
$C:=256(2d+1)^{2}$, $D$ has a bisection $V(D)=W_{1}\cup W_{2}$ such that
$X_{i}\subseteq W_{i}$ for $i=1,2$, and moreover (note that $e(X)=0$)

$\displaystyle\min\\{e(W_{1},W_{2}),e(W_{2},W_{1})\\}$ $\displaystyle\geq\;$
$\displaystyle\frac{1}{2}\min\\{e(X_{1},Y)+e(Y,X_{2}),e(X_{2},Y)+e(Y,X_{1})\\}+\frac{e(Y)}{4}+\frac{n-\tau}{8}-\frac{\varepsilon}{4}n$
$\displaystyle=\;$
$\displaystyle\frac{e(X,Y)+e(Y,X)-\theta}{4}+\frac{e(Y)}{4}+\frac{n-\tau}{8}-\frac{\varepsilon}{4}n$
$\displaystyle=\;$
$\displaystyle\frac{m-\theta}{4}+\frac{n-\tau}{8}-\frac{\varepsilon}{4}n$
$\displaystyle\geq\;$
$\displaystyle\frac{m-\theta}{4}+\frac{n-\tau}{8}-\frac{\varepsilon}{2}m,$

where the last inequality holds as $m\geq dn/2\geq n/2$ from (3.2). To prove
(3.3) (and thus Theorem 1.4), it suffices to show that

$\frac{m-\theta}{4}+\frac{n-\tau}{8}-\frac{\varepsilon}{2}m\geq\Big{(}\frac{d}{2(2d+1)}-\frac{\varepsilon}{2}\Big{)}m,$

which is equivalent to the following

$\frac{m}{2d+1}+\frac{n}{2}-\theta-\frac{\tau}{2}\geq 0.$ (3.6)

Note that we have $\tau\leq n$. If $\theta\leq\frac{m}{2d+1}$, then (3.6)
holds trivially. So we may assume

$\theta>\frac{m}{2d+1}>0.$ (3.7)

We point out that since $\theta>0$, it follows from (3.5) that $X$ has at
least one forward vertex.

Our strategy in the coming proof then is to prove (3.6) by establishing a
sequence of claims. The following two claims can be found in [18] whose proofs
can be traced back to [26]. For the sake of completeness, we include their
short proofs here.

######  Claim 3.1.

Call a vertex $v\in X$ huge if $s(v)\geq\theta$. Then all forward vertices in
$X$ are huge. In particular, there is at least one huge vertex.

###### Proof.

As we just point out after (3.7), there is at least one forward vertex in $X$.
Take any forward vertex $v\in X$. By definition, $s(v)>0$. Let
$X^{\prime}_{1}\cup X^{\prime}_{2}$ be the new partition of $X$ obtained from
$X_{1}\cup X_{2}$ by switching the side of $v$. Then

$\displaystyle\theta(X^{\prime}_{1},X^{\prime}_{2})=\;$
$\displaystyle\big{(}e(X^{\prime}_{1},Y)+e(Y,X^{\prime}_{2})\big{)}-\big{(}e(X^{\prime}_{2},Y)+e(Y,X^{\prime}_{1})\big{)}$
$\displaystyle=\;$
$\displaystyle\big{(}e(X_{1},Y)+e(Y,X_{2})-s(v)\big{)}-\big{(}e(X_{2},Y)+e(Y,X_{1})+s(v)\big{)}=\theta-2s(v).$

Since $X_{1}\cup X_{2}$ is a partition of $X$ minimizing
$|\theta(X_{1},X_{2})|$, we have
$|\theta(X^{\prime}_{1},X^{\prime}_{2})|=|\theta-2s(v)|\geq\theta$. This
forces $s(v)\geq\theta$, which means $v$ is huge. ∎

Let $X^{\prime}$ be the set of huge vertices in $X$. By Claim 3.1, we know
that all vertices in $X\backslash X^{\prime}$ are backward vertices. Define

$\alpha=|X^{\prime}|~{}~{}\mbox{ and }~{}~{}g=\sum_{v\in X\backslash
X^{\prime}}s(v).$

######  Claim 3.2.

For any forward vertex $v\in X$, we have $s(v)\geq\theta+g$.

###### Proof.

For the bipartition $X=X_{1}\cup X_{2}$, we call an arc in
$(X_{1},Y)\cup(Y,X_{2})$ forward and an arc in $(X_{2},Y)\cup(Y,X_{1})$
backward. Let $m_{f}=e(X_{1},Y)+e(Y,X_{2})$ and $m_{b}=e(X_{2},Y)+e(Y,X_{1})$.
Note that $\theta=m_{f}-m_{b}$.

Suppose to the contrary that there exists a forward vertex $v\in X$ such that
$g>s(v)-\theta\geq 0$. Recall that $g=\sum_{v\in X\backslash X^{\prime}}s(v)$.
Then $X\backslash X^{\prime}=\\{u\in X:s(u)<\theta\\}\neq\emptyset$. Now we
switch vertices between $X_{1}$ and $X_{2}$ in two consecutive rounds. First,
we move $v$ to the other part of the partition $X=X_{1}\cup X_{2}$. Then the
number of forward arcs in the resulting partition of $X$ becomes
$m_{f}^{\prime}=m_{f}-s(v)\leq m_{f}-\theta=m_{b}$. Next, we choose a vertex
in $X\backslash X^{\prime}$ (which remains backward) at a time and switch it
to the other part. After we switch all vertices in $X\backslash X^{\prime}$,
the number of forward arcs becomes
$m_{f}^{\prime\prime}=m_{f}^{\prime}+g=m_{f}-s(v)+g>m_{f}-s(v)+(s(v)-\theta)=m_{f}-\theta=m_{b}$.

In the second round, when the first time the number of forward arcs
$m_{f}^{*}$ is greater than $m_{b}$, it must be the case that
$m_{f}^{*}<m_{b}+\theta=m_{f}$. Note that during the above switching process,
the number of forward and backward arcs in total always equals to
$m_{f}+m_{b}$. This tells that at the very same moment, the number of backward
arcs $m_{b}^{*}$ also satisfies $m_{b}<m_{b}^{*}<m_{f}$. So we get
$|m_{f}^{*}-m_{b}^{*}|<|m_{f}-m_{b}|=\theta$, contradicting the minimality of
the gap $\theta$. This proves that $s(v)\geq\theta+g$. ∎

###  3.3 Bounding the arcs between $X$ and $Y$

We turn to some key estimations on the sizes of $(X,Y)$ and $(Y,X)$, which
provide new ingredients to Question 1.3. Recall that $\tau$ denotes the number
of essential components in $D[Y]$.

######  Claim 3.3.

$(2d+1)\tau\leq|Y|+2\cdot\min\\{e(X,Y),e(Y,X)\\}$.

###### Proof.

For $i=1,3,\ldots,2d-1$, let $\tau_{i}$ be the number of essential components
in $D[Y]$ of order $i$; and let $\tau^{\prime}$ be the number of essential
components in $D[Y]$ of order at least $2d+1$. Then

$\tau=\sum_{i=1}^{d}\tau_{2i-1}+\tau^{\prime}.$ (3.8)

Considering the number of vertices in $Y$, it yields that

$\sum_{i=1}^{d}(2i-1)\tau_{2i-1}+(2d+1)\tau^{\prime}\leq|Y|.$ (3.9)

Now we count the number of arcs from $Y$ to $X$. For each essential component
$D_{i}$ of order $i$, as it does not contain two arcs in opposite directions,
we have $e(D_{i})\leq i(i-1)/2$. Thus, since the outdegree of every vertex in
$Y$ is at least $d$, we see that $e(D_{i},X)\geq di-i(i-1)/2$. Viewing
$f(i)=di-i(i-1)/2$ as a function of $i$ over the interval $[1,2d-1]$, we see
that it achieves its minimum at $i=1$ (since $d\geq 1$). Hence,
$e(D_{i},X)\geq f(1)=d$ for every $i\in[2d-1]$. Thus,

$\sum_{i=1}^{d}d\cdot\tau_{2i-1}\leq e(Y,X).$ (3.10)

Combining (3.8), (3.9) with (3.10), we can derive that

$(2d+1)\tau\;\leq\;\sum_{i=1}^{d}(2d+2i-1)\tau_{2i-1}+(2d+1)\tau^{\prime}\leq|Y|+2e(Y,X).$

Note that the indegree of each vertex in $Y$ is also at least $d$. Using the
same arguments as above, counting the number of arcs from $X$ to $Y$ would
lead to

$(2d+1)\tau\leq|Y|+2e(X,Y),$

proving the claim. ∎

For convenience, we define

$e_{X,Y}:=e(X,Y)+e(Y,X)~{}~{}\mbox{and}~{}~{}b=\sum_{v\in
X}\min\\{d^{+}(v),d^{-}(v)\\}.$

For any $v\in X$, we have $d(v)-s(v)=2\min\\{d^{+}(v),d^{-}(v)\\}.$ Therefore

$m\geq m-e(Y)=e_{X,Y}=\sum_{v\in X}d(v)=\sum_{v\in X}s(v)+2b=\sum_{v\in
X^{\prime}}s(v)+g+2b\geq\alpha\theta,$ (3.11)

where $\alpha=|X^{\prime}|$ denotes the number of huge vertices in $X$. By
Claim 3.1, we have

$1\leq\alpha\leq\frac{m}{\theta}<2d+1,$ (3.12)

where the second inequality holds because of (3.11) and the third inequality
follows from (3.7).

Let $X^{\prime}=\\{v_{1},v_{2},\ldots,v_{\alpha}\\}$ with
$s(v_{i})=\Delta_{i}$ for $i\in[\alpha]$ such that
$\Delta_{1}\geq\Delta_{2}\geq\cdots\geq\Delta_{\alpha}\geq\theta$. After (3.7)
we point out that there exists at least one forward vertex (say $v_{i}\in
X^{\prime}$). By Claim 3.2, $\Delta_{i}=s(v_{i})\geq\theta+g$ and thus we have

$0\leq g\leq\Delta_{1}-\theta.$ (3.13)

Throughout we let $\beta=\lceil\alpha/2\rceil$. By (3.12), we see
$1\leq\beta\leq d$.

######  Claim 3.4.

$\max\\{e(X,Y),e(Y,X)\\}\geq\beta\theta+b$ and
$\min\\{e(X,Y),e(Y,X)\\}\leq\sum_{i=1}^{\alpha}\Delta_{i}+g-\beta\theta+b$.

###### Proof.

There always exist $\beta$ vertices in $X^{\prime}$, say
$X^{*}=\\{v_{j_{1}},v_{j_{2}},\ldots,v_{j_{\beta}}\\}$, satisfying either (i)
$s(v_{j_{i}})=s^{+}(v_{j_{i}})$ for every $i\in[\beta]$, or (ii)
$s(v_{j_{i}})=s^{-}(v_{j_{i}})$ for every $i\in[\beta]$.

If the case (i) occurs, then
$s(v_{j_{i}})=s^{+}(v_{j_{i}})=d^{+}(v_{j_{i}})-d^{-}(v_{j_{i}})\geq\theta$
for $i\in[\beta]$, implying

$\displaystyle e(X,Y)=$ $\displaystyle\sum_{v\in X}d^{+}(v)$ $\displaystyle=$
$\displaystyle\sum_{v\in{X^{*}}}d^{+}(v)+\sum_{v\in{X\backslash
X^{*}}}d^{+}(v)$ $\displaystyle\geq$
$\displaystyle\sum_{v\in{X^{*}}}(d^{-}(v)+\theta)+\sum_{v\in{X\backslash
X^{*}}}d^{+}(v)$ $\displaystyle\geq$ $\displaystyle\beta\theta+\sum_{v\in
X}\min\\{d^{+}(v),d^{-}(v)\\}$ $\displaystyle=$ $\displaystyle\beta\theta+b.$

If the case (ii) occurs, by the similar arguments we can obtain that
$e(Y,X)\geq\beta\theta+b.$ This shows that
$\max\\{e(X,Y),e(Y,X)\\}\geq\beta\theta+b$. Finally, using (3.11) we have

$\max\\{e(X,Y),e(Y,X)\\}+\min\\{e(X,Y),e(Y,X)\\}=e_{X,Y}=\sum_{v\in
X}s(v)+2b=\sum_{i=1}^{\alpha}\Delta_{i}+g+2b,$

which implies that
$\min\\{e(X,Y),e(Y,X)\\}\leq\sum_{i=1}^{\alpha}\Delta_{i}+g-\beta\theta+b$, as
desired. ∎

The next claim gives a further upper bound on $\min\\{e(X,Y),e(Y,X)\\}$.

######  Claim 3.5.

$\min\\{e(X,Y),e(Y,X)\\}\leq 2\beta\Delta_{1}-(\beta+1)\theta+b,$ where
$1\leq\beta\leq d$.

###### Proof.

For clarity of presentation we divide this proof into two cases according to
the parity of $\alpha$. First assume that $\alpha$ is odd. Then
$\alpha=2\beta-1$ where $\beta\in[1,d]$. It follows from Claim 3.4 and (3.13)
that

$\displaystyle\min\\{e(X,Y),e(Y,X)\\}\leq\sum_{i=1}^{2\beta-1}\Delta_{i}+g-\beta\theta+b\leq
2\beta\Delta_{1}-(\beta+1)\theta+b.$

It remains to consider when $\alpha$ is even. Then $\alpha=2\beta$, where
$\beta\in[1,d]$. Recall (3.5) and the definitions of $X_{f},X_{b}$. Let
$v_{p_{1}},v_{p_{2}},\ldots,v_{p_{s}}$ be all forward vertices in $X^{\prime}$
and $v_{q_{1}},v_{q_{2}},\ldots,v_{q_{t}}$ be all backward vertices in
$X^{\prime}$, where $s+t=|X^{\prime}|=2\beta$. By Claim 3.1, all vertices in
$X\backslash X^{\prime}$ are backward vertices. Hence,

$X_{f}=\\{v_{p_{1}},v_{p_{2}},\ldots,v_{p_{s}}\\}~{}\mbox{ and
}~{}X_{b}=\\{v_{q_{1}},v_{q_{2}},\ldots,v_{q_{t}}\\}\cup X\backslash
X^{\prime}.\ $

Then by (3.5) and the definition of $g$, we have

$\theta=\sum_{v\in X_{f}}s(x)-\sum_{v\in
X_{b}}s(x)=\sum_{i=1}^{s}\Delta_{p_{i}}-\sum_{i=1}^{t}\Delta_{q_{i}}-g.$
(3.14)

By Claim 3.4, we get

$\min\\{e(X,Y),e(Y,X)\\}\leq\sum_{i=1}^{\alpha}\Delta_{i}+g-\beta\theta+b=\sum_{i=1}^{s}\Delta_{p_{i}}+\sum_{i=1}^{t}\Delta_{q_{i}}+g-\beta\theta+b$
(3.15)

If $s\leq\beta$, then using (3.14) the above inequality implies

$\min\\{e(X,Y),e(Y,X)\\}\leq
2\sum_{i=1}^{s}\Delta_{p_{i}}-\theta-\beta\theta+b\leq
2\beta\Delta_{1}-(\beta+1)\theta+b,$

as desired. So $s\geq\beta+1$. Then $t=2\beta-s\leq\beta-1$. Using the
equivalent form
$\sum_{i=1}^{s}\Delta_{p_{i}}=\theta+\sum_{i=1}^{t}\Delta_{q_{i}}+g$ of
(3.14), the inequality (3.15) gives that

$\min\\{e(X,Y),e(Y,X)\\}\leq
2\sum_{i=1}^{t}\Delta_{q_{i}}+2g+\theta-\beta\theta+b\leq
2(t+1)\Delta_{1}-(\beta+1)\theta+b\leq 2\beta\Delta_{1}-(\beta+1)\theta+b,$

where the second last inequality holds by (3.13). This claim now is complete.
∎

###  3.4 Completing the proof

Finally, we are ready to complete the proof by showing (3.6).

We will need one more inequality that

$m\geq\beta\theta+b+d|Y|.$ (3.16)

To see this, since $\delta^{0}(D)=\min\\{\delta^{+}(D),\delta^{-}(D)\\}\geq
d$, we have $e(Y,X)+e(Y)\geq d|Y|$ and $e(X,Y)+e(Y)\geq d|Y|.$ That says,

$\min\\{e(X,Y),e(Y,X)\\}+e(Y)\geq d|Y|.$

Indeed, this together with Claim 3.4 give the desired inequality that

$m=e_{X,Y}+e(Y)=\max\\{e(X,Y),e(Y,X)\\}+\min\\{e(X,Y),e(Y,X)\\}+e(Y)\geq\beta\theta+b+d|Y|.$

We can also derive from Claims 3.3 and 3.5 that

$(2d+1)\tau\leq|Y|+4\beta\Delta_{1}-2(\beta+1)\theta+2b.$ (3.17)

Since $e(X)=0$, we see
$|Y|\geq|d^{+}(v_{1})-d^{-}(v_{1})|=s(v_{1})=\Delta_{1}$. This together with
(3.13) imply that $n\geq|Y|\geq\Delta_{1}\geq\theta$. Also note that
$d\geq\beta$. Then using (3.16) and (3.17) we have

$\displaystyle
2(2d+1)\left(\frac{m}{2d+1}+\frac{n}{2}-\theta-\frac{\tau}{2}\right)$
$\displaystyle\geq\;$ $\displaystyle 2m+(2d+1)|Y|-(4d+2)\theta-(2d+1)\tau$
$\displaystyle\geq\;$
$\displaystyle\Big{(}2\beta\theta+2b+2d|Y|\Big{)}+(2d+1)|Y|-(4d+2)\theta-\Big{(}|Y|+4\beta\Delta_{1}-2(\beta+1)\theta+2b\Big{)}$
$\displaystyle=\;$ $\displaystyle 4d|Y|-4\beta\Delta_{1}-4(d-\beta)\theta$
$\displaystyle\geq\;$ $\displaystyle 0.$

Hence (3.6) holds. This completes the proof of Theorem 1.4.

##  4 Concluding remarks

In this paper, we answer Question 1.3 by showing that every digraph $D$ with
$m$ arcs and minimum semidegree $d$ admits a bisection $V(D)=V_{1}\cup V_{2}$
such that
$\min\\{e(V_{1},V_{2}),e(V_{2},V_{1})\\}\geq\frac{d}{2(2d+1)}m+o(m)$. Most
arguments in Section 3 in fact work for any digraph which may be useful for
Conjecture 1.2 (to be precise, only Claim 3.3 and Subsection 3.4 use the
minimum semidegree condition). We also wonder if the following can be true.

######  Question 4.1.

Is it true that for every integer $d\geq 1$ and sufficiently large $m$, every
digraph $D$ with $m$ arcs and minimum semidegree $d$ admits a bipartition
$V(D)=V_{1}\cup V_{2}$ such that

$\min\left\\{e(V_{1},V_{2}),e(V_{2},V_{1})\right\\}\geq\frac{d}{2(2d+1)}m.$

One plausible step towards this question is to remove the term $\varepsilon n$
in Lemma 2.7. It may also be the case that such a bipartition can be replaced
by a bisection.

## References

  * [1]
  * [2] N. Alon, Bipartite subgraphs, Combinatorica 16 (1996) 301–311.
  * [3] N. Alon, B. Bollobás, M. Krivelevich and B. Sudakov, Maximum cuts and judicious partitions in graphs without short cycles, J. Combin. Theory Ser. B 88 (2003) 329–346.
  * [4] N. Alon, B. Bollobás, A. Gyárfás, J. Lehel and A. Scott, Maximum directed cuts in acyclic digraphs, J. Graph Theory 55 (2007) 1–13.
  * [5] K. Azuma, Weighted sums of certain dependent random variables, Tokuku Math. J. 19 (1967) 357–367.
  * [6] B. Bollobás and A.D. Scott, Judicious partitions of hypergraphs, J. Combin. Theory Ser. A 78 (1997) 15–31.
  * [7] B. Bollobás and A.D. Scott, Exact bounds for judicious partitions of graphs, Combinatorica 19 (1999) 473–486.
  * [8] B. Bollobás and A.D. Scott, Judicious partitions of 3-uniform hypergraphs, Eur. J. Comb. 21 (2000) 289–300.
  * [9] B. Bollobás and A.D. Scott, Problems and results on judicious partitions, Random Struct. Alg. 21 (2002) 414–430.
  * [10] B. Bollobás and A.D. Scott, Judicious partitions of bounded-degree graphs, J. Graph Theory 46 (2004) 131–143.
  * [11] C. Edwards, Some extremal properties of bipartite graphs, Canad. J. Math. 3 (1973) 475–485.
  * [12] C. Edwards, An improved lower bound for the number of edges in a largest bipartite subgraph, Proc. 2nd Czechoslovak Symposium on Graph Theory (1975) 167–181.
  * [13] G. Fan and J. Hou, Bounds for pairs in judicious partitioning of graphs, Random Struct. Alg. 50 (2017) 59–70.
  * [14] G. Fan, J. Hou and X. Yu, Bisections of graphs without short cycles. Combin. Probab. Comput. 27 (2018) 44–59.
  * [15] J. Haslegrave, The Bollobás-Thomason conjecture for 3-uniform hypergraphs. Combinatorica 32 (2012) 451–471.
  * [16] J. Haslegrave, Judicious partitions of uniform hypergraphs. Combinatorica 34 (2014) 561–572.
  * [17] W. Hoeffding, Probability inequalities for sums of bounded random variables, J. Amer. Statist. Assoc. 58 (1963) 13–30.
  * [18] J. Hou, Z. Li and S. Wu, On bipartitions of directed graphs with small semidegree, European J. Combin. 84 (2020) 103039.
  * [19] J. Hou, H. Ma, X. Yu and X. Zhang, A bound on judicious of directed graphs, Sci. China Math. 63 (2020) 297–308.
  * [20] J. Hou and S. Wu, Bipartitions of oriented graphs, J. Combin. Theory Ser. B 132 (2018) 107–133.
  * [21] J. Hou and S. Wu, On bisections of graphs without complete bipartite graphs. J. Graph Theory 98 (2021) 630–641.
  * [22] J. Hou, S. Wu and G. Yan, On judicious partitions of uniform hypergraphs, J. Combin. Theory Ser. A 141 (2016) 16–32.
  * [23] J. Hou, S. Wu and G. Yan, On bisections of directed graphs, European J. Combin. 63 (2017) 44–58.
  * [24] Y. Ji, J. Ma, J. Yan and X. Yu, On problems about judicious bipartitions of graphs, J. Combin. Theory Ser. B 132 (2018) 107–133.
  * [25] C. Lee, P. Loh and B. Sudakov, Bisections of graphs, J. Combin. Theory Ser. B 103 (2013) 599–629.
  * [26] C. Lee, P. Loh and B. Sudakov, Judicious partitions of directed graphs, Random Struct. Alg. 48 (2016) 147–170.
  * [27] J. Lin and Q. Zeng, Maximum bisections of graphs without short even cycles, J. Combin. Theory Ser. A 180 (2021) 105404.
  * [28] G. Liu and X. Yu, Partitioning digraphs with outdegree at least 4, J. Graph Theory 98 (2021) 604–622.
  * [29] J. Ma, P. Yen and X. Yu, On several partitioning problems of Bollobás and Scott, J. Combin. Theory Ser. B 100 (2010) 631–649.
  * [30] J. Ma and X. Yu, Partitioning 3-uniform hypergraphs, J. Combin. Theory Ser. B 102 (2012) 212–232.
  * [31] J. Ma and X. Yu, On judicious bipartitions of graphs, Combinatorica 36 (2016) 537–556.
  * [32] D. Porter, On a bottleneck bipartition conjecture of Erdös, Combinatorica 12 (1992) 317–321.
  * [33] A. Scott, Judicious partitions and related problems, Surveys in combinatorics 327 (2005) 95–117.
  * [34] H. Spink and M. Tiba, Judiciously 3-partitioning 3-uniform hypergraphs, Random Struct. Alg. 56 (2020) 1205–1221.
  * [35] S. Wu and J. Hou, Graph partitioning: an updated survey, AKCE International Journal of Graphs and Combinatorics, DOI: 10.1080/09728600.2022.2148589.
  * [36] B. Xu and X. Yu, Better bounds for $k$-partitions of graphs, Combin. Probab. Comput. 20 (2011) 631–640.
  * [37] B. Xu and X. Yu, On judicious bisections of graphs, J. Combin. Theory Ser. B 106 (2014) 30–69.

E-mail address<EMAIL_ADDRESS>
E-mail address<EMAIL_ADDRESS>
E-mail address<EMAIL_ADDRESS>


HepG2 | 0.85 | 0.79 | 0.78 | 0.84 | 0.80 | 0.83 | 0.82 | 0.83 | 0.86 | 0.84 | 0.81 | 0.84 | 0.82 | 0.85
HMEC | 0.80 | 0.71 | 0.68 | 0.77 | 0.72 | 0.76 | 0.74 | 0.76 | 0.79 | 0.76 | 0.73 | 0.77 | 0.75 | 0.78
HSMM | 0.84 | 0.72 | 0.65 | 0.80 | 0.71 | 0.75 | 0.74 | 0.77 | 0.83 | 0.78 | 0.73 | 0.79 | 0.76 | 0.81
HSMMtube | 0.83 | 0.74 | 0.69 | 0.80 | 0.73 | 0.77 | 0.76 | 0.78 | 0.84 | 0.79 | 0.74 | 0.79 | 0.77 | 0.82
HUVEC | 0.86 | 0.75 | 0.69 | 0.83 | 0.75 | 0.79 | 0.78 | 0.81 | 0.85 | 0.81 | 0.77 | 0.82 | 0.79 | 0.84
K562 | 0.76 | 0.73 | 0.69 | 0.78 | 0.71 | 0.74 | 0.73 | 0.75 | 0.81 | 0.75 | 0.72 | 0.77 | 0.74 | 0.77
LNCaP | 0.74 | 0.71 | 0.67 | 0.75 | 0.68 | 0.70 | 0.69 | 0.71 | 0.77 | 0.73 | 0.68 | 0.73 | 0.70 | 0.76
MCF-7 | 0.80 | 0.69 | 0.67 | 0.77 | 0.69 | 0.73 | 0.72 | 0.74 | 0.79 | 0.75 | 0.71 | 0.75 | 0.72 | 0.77
NHEK | 0.86 | 0.72 | 0.67 | 0.81 | 0.74 | 0.79 | 0.77 | 0.80 | 0.85 | 0.80 | 0.76 | 0.81 | 0.78 | 0.83
Th1 | 0.77 | 0.75 | 0.74 | 0.78 | 0.76 | 0.77 | 0.76 | 0.77 | 0.78 | 0.78 | 0.76 | 0.78 | 0.77 | 0.78
Table A10: Histone modification prediction performance per label. Modifiation (label no.) |  Basset |  CNN |  AWD-LSTM |  ResNet-LM |  NT-H |  NT-MS |  NT-1000G (2.5B) |  NT-V2 |  DNABERT |  DNABERT-2 |  GENA-LM BERT |  GENA-LM BigBird |  HyenaDNA tiny |  HyenaDNA large
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
H3K27me3_K562 (0) | 0.63 | 0.67 | 0.66 | 0.7 | 0.69 | 0.7 | 0.69 | 0.68 | 0.72 | 0.7 | 0.7 | 0.71 | 0.68 | 0.67
H3K9ac_K562 (1) | 0.87 | 0.85 | 0.85 | 0.87 | 0.86 | 0.86 | 0.87 | 0.86 | 0.87 | 0.86 | 0.86 | 0.87 | 0.87 | 0.87
H3K9me3_K562 (2) | 0.74 | 0.77 | 0.75 | 0.84 | 0.83 | 0.83 | 0.83 | 0.78 | 0.83 | 0.84 | 0.86 | 0.86 | 0.79 | 0.8
H3K4me1_K562 (3) | 0.65 | 0.67 | 0.65 | 0.68 | 0.67 | 0.68 | 0.67 | 0.67 | 0.71 | 0.69 | 0.67 | 0.69 | 0.67 | 0.67
H3K9ac_K562 (4) | 0.74 | 0.75 | 0.7 | 0.74 | 0.73 | 0.75 | 0.74 | 0.74 | 0.77 | 0.75 | 0.75 | 0.75 | 0.74 | 0.74
H3K4me1_K562 (5) | 0.8 | 0.8 | 0.8 | 0.81 | 0.81 | 0.81 | 0.81 | 0.8 | 0.82 | 0.81 | 0.8 | 0.81 | 0.81 | 0.81
H3K36me3_K562 (6) | 0.63 | 0.65 | 0.62 | 0.7 | 0.7 | 0.74 | 0.71 | 0.66 | 0.7 | 0.72 | 0.73 | 0.74 | 0.65 | 0.67
H3K36me3_K562 (7) | 0.75 | 0.77 | 0.75 | 0.78 | 0.77 | 0.79 | 0.77 | 0.77 | 0.78 | 0.78 | 0.78 | 0.79 | 0.76 | 0.77
H4K20me1_K562 (8) | 0.62 | 0.69 | 0.69 | 0.71 | 0.69 | 0.71 | 0.69 | 0.69 | 0.72 | 0.71 | 0.7 | 0.72 | 0.69 | 0.69
H3K27me3_K562 (9) | 0.74 | 0.74 | 0.75 | 0.8 | 0.79 | 0.8 | 0.8 | 0.79 | 0.8 | 0.79 | 0.8 | 0.8 | 0.78 | 0.77
H3K4me3_K562 (10) | 0.88 | 0.89 | 0.87 | 0.89 | 0.88 | 0.89 | 0.89 | 0.89 | 0.9 | 0.89 | 0.89 | 0.89 | 0.89 | 0.89
H3K4me3_K562 (11) | 0.89 | 0.89 | 0.87 | 0.89 | 0.89 | 0.89 | 0.89 | 0.89 | 0.9 | 0.89 | 0.89 | 0.89 | 0.89 | 0.89
H3K4me3_K562 (12) | 0.84 | 0.85 | 0.82 | 0.85 | 0.84 | 0.85 | 0.85 | 0.84 | 0.86 | 0.85 | 0.85 | 0.85 | 0.85 | 0.85
H3K4me3_K562 (13) | 0.76 | 0.77 | 0.72 | 0.77 | 0.75 | 0.77 | 0.76 | 0.76 | 0.8 | 0.77 | 0.77 | 0.78 | 0.76 | 0.75
H3K79me2_K562 (14) | 0.74 | 0.76 | 0.75 | 0.76 | 0.76 | 0.76 | 0.76 | 0.75 | 0.76 | 0.76 | 0.76 | 0.77 | 0.76 | 0.7
H3K4me2_K562 (15) | 0.7 | 0.72 | 0.67 | 0.71 | 0.7 | 0.72 | 0.71 | 0.71 | 0.75 | 0.73 | 0.71 | 0.72 | 0.7 | 0.7
H3K27ac_K562 (16) | 0.7 | 0.72 | 0.67 | 0.71 | 0.7 | 0.72 | 0.7 | 0.71 | 0.76 | 0.73 | 0.71 | 0.72 | 0.71 | 0.71
H2AFZ_K562 (17) | 0.7 | 0.71 | 0.67 | 0.72 | 0.71 | 0.73 | 0.71 | 0.71 | 0.75 | 0.73 | 0.73 | 0.73 | 0.7 | 0.7
Table A11: CpG methylation prediction performance per cell line.

Model SK-N-SH GM23248 A549 HepG2 HUES64 GM23248 HeLa-S3 ENCFF567KCL
ENCFF170XYJ ENCFF948WVD ENCFF690FNR ENCFF890GMD ENCFF840XVU ENCFF754RAW Basset
0.93 0.94 0.93 0.90 0.95 0.94 0.93 CNN 0.84 0.84 0.84 0.82 0.93 0.84 0.83
ResNet-LM 0.86 0.87 0.86 0.85 0.94 0.87 0.86 AWD-LSTM 0.80 0.80 0.80 0.78 0.89
0.80 0.79 NT-H 0.87 0.87 0.87 0.85 0.94 0.87 0.87 NT-MS 0.92 0.92 0.92 0.89
0.96 0.92 0.91 NT-1000G (2.5B) 0.88 0.88 0.88 0.86 0.94 0.88 0.87 NT-V2 0.90
0.91 0.90 0.88 0.96 0.91 0.90 DNABERT 0.91 0.91 0.91 0.88 0.96 0.91 0.90
DNABERT-2 0.89 0.89 0.89 0.87 0.96 0.89 0.89 GENA-LM BERT 0.91 0.91 0.91 0.89
0.95 0.91 0.90 GENA-LM BigBird 0.90 0.91 0.90 0.88 0.95 0.91 0.90 HyenaDNA
tiny 0.85 0.85 0.85 0.83 0.92 0.85 0.84 HyenaDNA large 0.91 0.91 0.91 0.88
0.94 0.91 0.90

Table A12: Variant effect prediction performance (AUROC) on the expression
variant effect prediction dataset, stratified by variant category. Categories
that only have samples of one label were ommitted as no AUC can be determined.
For completeness, also AUROCs on categories with very low sample numbers are
reported, but should be interpreted with caution.

Model Intron (n=61,229) Intergenic (n=23,379) Upstream gene (n=6,433)
Downstream gene (n=4,645) Regulatory region (n=4,049) Noncoding transcript
exon (n=3,141) 3’ UTR (n=2,049) 5’ UTR (n=470) TF binding site (n=436) Splice
region (n=131) Splice polypyrimidine tract (n=105) Missense (n=62) Splice
donor region (n=31) Synonymous (n=24) Splice donor (n=15) Splice donor 5th
base (n=13) Stop lost (n=2) DeepSEA 0.7 0.69 0.71 0.71 0.71 0.68 0.64 0.72
0.64 0.55 0.62 0.72 0.46 0.54 0.35 0.83 1.00 ResNet-LM 0.55 0.54 0.56 0.55
0.52 0.51 0.54 0.45 0.46 0.45 0.55 0.51 0.69 0.70 0.50 0.50 1.00 AWD-LSTM 0.51
0.51 0.50 0.52 0.49 0.51 0.52 0.52 0.42 0.52 0.57 0.58 0.62 0.65 0.62 0.55
0.00 NT-H 0.55 0.54 0.55 0.54 0.53 0.52 0.49 0.43 0.44 0.52 0.34 0.58 0.36
0.71 0.50 0.67 1.00 NT-MS 0.55 0.53 0.54 0.55 0.55 0.56 0.57 0.49 0.54 0.54
0.52 0.56 0.56 0.65 0.19 0.60 1.00 NT-1000G-2.5B 0.44 0.43 0.44 0.44 0.48 0.46
0.48 0.44 0.47 0.43 0.42 0.46 0.39 0.54 0.27 0.21 1.00 NT-1000G-500M 0.49 0.48
0.49 0.47 0.50 0.53 0.50 0.46 0.51 0.52 0.50 0.42 0.66 0.29 0.46 0.33 0.00
NT-V2-500M 0.49 0.47 0.47 0.48 0.51 0.48 0.50 0.41 0.51 0.59 0.55 0.36 0.51
0.68 0.77 0.40 0.00 DNABERT 0.60 0.59 0.61 0.60 0.58 0.57 0.55 0.60 0.51 0.52
0.70 0.57 0.77 0.88 0.69 0.45 0.00 DNABERT-2 0.49 0.49 0.48 0.49 0.53 0.48
0.48 0.53 0.58 0.50 0.48 0.57 0.78 0.59 0.35 0.52 1.00 GENA-LM BERT 0.49 0.49
0.50 0.50 0.55 0.51 0.51 0.50 0.55 0.52 0.48 0.55 0.27 0.29 0.58 0.60 0.00
GENA-LM BigBird 0.49 0.48 0.49 0.49 0.53 0.51 0.52 0.50 0.53 0.52 0.48 0.55
0.24 0.43 0.35 0.55 0.00 HyenaDNA large 0.51 0.52 0.50 0.52 0.53 0.51 0.50
0.50 0.48 0.49 0.51 0.49 0.35 0.29 0.19 0.36 0.00 HyenaDNA medium (160k) 0.49
0.50 0.47 0.50 0.52 0.49 0.49 0.48 0.47 0.49 0.51 0.54 0.33 0.31 0.23 0.36
0.00 HyenaDNA medium (450k) 0.50 0.51 0.50 0.51 0.53 0.50 0.50 0.48 0.46 0.48
0.54 0.54 0.39 0.29 0.19 0.43 0.00 HyenaDNA small 0.46 0.47 0.45 0.47 0.50
0.47 0.48 0.47 0.49 0.49 0.48 0.41 0.32 0.25 0.19 0.36 0.00 HyenaDNA tiny 0.47
0.48 0.44 0.49 0.51 0.49 0.48 0.48 0.51 0.49 0.48 0.40 0.34 0.35 0.27 0.24
0.00

Table A13: Variant effect prediction performance (AUROC) on the disease
variant effect prediction dataset, stratified by variant category. Categories
that only have samples of one label were ommitted as no AUC can be determined.
For completeness, also AUCs on categories with very low sample numbers are
reported, but should be interpreted with caution.

Model Intron (n=138,211) Splice region (n=40,360) Splice polypyrimidine tract
(n=39,686) Noncoding transcript exon (23,721) 3’ UTR (n=20,441) Splice donor
(n=10,811) Splice acceptor (n=9,280) 5’ UTR (n=6,996) Upstream gene (n=2,264)
Splice donor region (n=2,056) Splice donor 5th base (n=1,060) Downstream Gene
(n=274) Mature miRNA (n=40) Intergenic (n=20) DeepSEA 0.48 0.44 0.46 0.73 0.69
0.47 0.48 0.58 0.61 0.45 0.41 0.72 0.18 0.92 ResNet-LM 0.51 0.67 0.53 0.50
0.51 0.55 0.48 0.46 0.58 0.64 0.63 0.31 0.79 0.05 AWD-LSTM 0.46 0.41 0.47 0.55
0.50 0.51 0.51 0.48 0.47 0.52 0.50 0.44 0.44 0.16 NT-H 0.43 0.53 0.49 0.51
0.56 0.51 0.52 0.53 0.52 0.49 0.50 0.53 0.38 0.58 NT-MS 0.62 0.70 0.65 0.57
0.55 0.74 0.61 0.57 0.56 0.76 0.76 0.44 0.82 0.63 NT-1000G-2.5B 0.49 0.57 0.54
0.52 0.48 0.51 0.50 0.47 0.45 0.52 0.52 0.45 0.10 0.11 NT-1000G-500M 0.46 0.53
0.50 0.49 0.40 0.51 0.49 0.47 0.41 0.47 0.49 0.36 0.03 0.63 NT-V2-500M 0.50
0.52 0.49 0.50 0.36 0.49 0.53 0.52 0.46 0.50 0.43 0.54 0.33 0.21 DNABERT 0.52
0.55 0.47 0.48 0.63 0.54 0.51 0.62 0.58 0.55 0.56 0.62 0.72 0.05 DNABERT-2
0.48 0.46 0.53 0.54 0.49 0.50 0.52 0.45 0.51 0.45 0.52 0.51 0.92 0.95 GENA-LM
BERT 0.50 0.49 0.48 0.51 0.50 0.56 0.60 0.50 0.41 0.47 0.42 0.50 0.95 1.00
GENA-LM BigBird 0.48 0.48 0.46 0.51 0.52 0.54 0.60 0.46 0.45 0.48 0.43 0.60
1.00 0.89 HyenaDNA large 0.53 0.52 0.59 0.52 0.48 0.44 0.52 0.48 0.48 0.48
0.42 0.40 0.00 0.63 HyenaDNA medium 160k 0.52 0.54 0.60 0.54 0.46 0.44 0.51
0.46 0.50 0.47 0.41 0.41 0.00 0.47 HyenaDNA medium 450k 0.53 0.53 0.58 0.51
0.46 0.45 0.50 0.51 0.50 0.47 0.42 0.35 0.00 0.37 HyenaDNA small 0.53 0.54
0.59 0.53 0.47 0.44 0.49 0.46 0.53 0.48 0.41 0.44 0.10 0.42 HyenaDNA tiny 0.53
0.55 0.59 0.53 0.47 0.44 0.52 0.48 0.50 0.48 0.42 0.44 0.08 0.37

Table A14: Variant effect prediction performance on the disease variant effects prediction dataset with more stringent filtering. Variants labeled as ”Likely” in ClinVar were omitted, yielding a reduced dataset (Benign n=100,623, Pathogenic n=8,188). Similarly to the results on the full dataset, NT-MS outperforms DeepSEA. Additionally, ResNet-LM and DNABERT show strong performance. Model | AUC
---|---
DeepSEA | 0.57
ResNet-LM | 0.61
AWD-LSTM | 0.48
NT-H | 0.52
NT-MS | 0.74
NT-1000G-2.5B | 0.49
NT-1000G-500M | 0.46
NT-V2-500M | 0.48
DNABERT | 0.62
DNABERT2 | 0.50
GENA-LM BERT | 0.56
GENA-LM BigBird | 0.52
HyenaDNA large | 0.44
HyenaDNA medium 160k | 0.43
HyenaDNA medium 450k | 0.44
HyenaDNA small | 0.41
HyenaDNA tiny | 0.43