Lee–Loh–Sudakov two-way directed-cut conjecture
For every fixed integer and every , there exists such that every digraph with edges and minimum outdegree has a vertex bipartition satisfying and . Equivalently, both directed cuts have size at least as for fixed .
References
- Optimally large cuts in both directions — arXiv — Frederic Folz, Mykhaylo Tyomkyn
Source: arXiv
Progress summary
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 arcs and minimum outdegree at least has a bipartition with at least arcs in each direction across the cut. Their 2013 work established the asymptotic constants for and posed the remaining general case.
Known results
- : asymptotic bound ; : ; minimum outdegree tending to infinity: (Lee, Loh, and Sudakov, 2013).
- Under minimum indegree and outdegree both at least , the conjectured asymptotic bound was proved for (2018).
October 2026 claimed solution
Folz and Tyomkyn claim the sharp bound for minimum outdegree when is sufficiently large, with the case valid for every 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- general case remains open.
Solutions 0
No solutions have been posted yet.