← All problems

Lee–Loh–Sudakov two-way directed-cut conjecture

For every fixed integer d≥2d\ge 2 and every ε>0\varepsilon>0, there exists M=M(d,ε)M=M(d,\varepsilon) such that every digraph DD with m≥Mm\ge M edges and minimum outdegree δ+(D)≥d\delta^+(D)\ge d has a vertex bipartition V(D)=A∪˙BV(D)=A\mathbin{\dot\cup}B satisfying ∣E(A,B)∣≥(d−12(2d−1)−ε)m|E(A,B)|\ge\left(\frac{d-1}{2(2d-1)}-\varepsilon\right)m and ∣E(B,A)∣≥(d−12(2d−1)−ε)m|E(B,A)|\ge\left(\frac{d-1}{2(2d-1)}-\varepsilon\right)m. Equivalently, both directed cuts have size at least (d−12(2d−1)+o(1))m\left(\frac{d-1}{2(2d-1)}+o(1)\right)m as m→∞m\to\infty for fixed dd.

References

Source: arXiv

Progress summary

Refreshed
Open · solution reported

A 2026 specialist preprint claims to settle the asymptotic conjecture, but its general result applies only to sufficiently large graphs.

Lee, Loh, and Sudakov conjectured that every digraph with mm arcs and minimum outdegree at least dd has a bipartition with at least (d−12(2d−1)+o(1))m\left(\frac{d-1}{2(2d-1)}+o(1)\right)m arcs in each direction across the cut. Their 2013 work established the asymptotic constants for d=2,3d=2,3 and posed the remaining general case.

Known results

  • d=2d=2: asymptotic bound 16m\frac{1}{6}m; d=3d=3: 15m\frac{1}{5}m; minimum outdegree tending to infinity: 14m\frac{1}{4}m (Lee, Loh, and Sudakov, 2013).
  • Under minimum indegree and outdegree both at least dd, the conjectured asymptotic bound was proved for d=2,3d=2,3 (2018).

October 2026 claimed solution

Folz and Tyomkyn claim the sharp bound for minimum outdegree d≥2d\ge2 when mm is sufficiently large, with the d=2d=2 case valid for every mm and a near-extremal stability theorem. This would settle the conjectured asymptotic threshold, but the claim is unverified in the retrieved sources.

Current status (as of October 2026): The asymptotic minimum-outdegree conjecture is claimed solved but unverified; the unrestricted finite-mm general case remains open.

Sources

Solutions 0

No solutions have been posted yet.