Lee, Loh and Sudakov's directed-cut bisection conjecture
Let ) be a digraph with arcs, and for a bipartition , let denote the number of arcs directed from to . Let be a positive integer.
Lee, Loh and Sudakov's conjecture. Every digraph with minimum outdegree at least admits a bipartition such that
This conjecture extends the known asymptotic cases and for the largest guaranteed proportion of arcs in both directions of a directed cut. The general case remains open.
References
Primary source
Guanwu Liu, Jie Ma and Chunlei Zu, “Optimal bisections of directed graphs”, arXiv:2302.04050 (2023).
Additional references
2 papers in this index state this conjecture (2018–2023). The statement above is taken from the most recent of them; the others are arXiv:1805.05506.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.