For each fixed integer d≥ 1, determine the largest function F_d(m) such that, for every sufficiently large integer m and every digraph D with m arcs and minimum semidegree delta^0(D):=mindelta^+(D),delta^-(D)≥ d, there is a bisection V(D)=V_1 cup V_2 satisfying bigl|| V_1|-| V_2|bigr|≤ 1 and mine(V_1,V_2),e(V_2,V_1)≥ F_d(m). The claimed sharp bound is F_d(m)=dfracd(m+d+1)2(2d+1), with equality for infinitely many values of m for each fixed d.

Liu–Ma–Zu’s digraph bisection question

The question asks for the sharp guaranteed size of both directed parts of a bisection in a digraph with prescribed minimum semidegree. The earlier formulation is attributed to Hou and Wu; the supplied sources do not establish the Liu–Ma–Zu naming or provide a separate posing date.

Known results

Hou and Wu’s 2023 result proved the asymptotic semidegree bound with an $o(1)$ error and strengthened it to balanced bisections.
A 2013 result established related asymptotic bounds under minimum outdegree, including $d=2,3$ .
The minimum-outdegree- $4$ case was proved in 2020, with bound $\frac{3}{14}+o(1)$ times the number of arcs.

August 25, 2026 sharp-bound claim

A newly reported paper claims to remove the asymptotic error, retain balanced bisections, and prove that the additive term $d+1$ is sharp through infinitely many equality examples. Its principal theorem applies for each fixed $d$ and sufficiently large arc count; it also gives a separate universal sharp bound. The claim is not independently verified in the supplied sources.

Current status (as of August 2026): The asymptotic and balanced-bisection results are recorded, while the sharp exact theorem is claimed by the 2026 preprint but remains unverified.

Liu–Ma–Zu’s digraph bisection question

Primary source

Additional references

Progress summary

Solutions 0