Lee, Loh and Sudakov's directed-cut bisection conjecture
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.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
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.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.