Lee–Loh–Sudakov conjecture on judicious bipartitions of digraphs
Lee–Loh–Sudakov conjecture on judicious bipartitions of digraphs
For a digraph , let be its vertex set, let be its number of arcs, and let denote the number of arcs directed from to . A bipartition is a decomposition . Let be an integer satisfying .
Lee–Loh–Sudakov conjecture. Every digraph with arcs and minimum outdegree at least admits a bipartition with
This conjecture asks for the optimal asymptotic lower bound on the smaller of the two directed cut sizes in a digraph with prescribed minimum outdegree. Lee, Loh, and Sudakov proved the corresponding asymptotic values for minimum outdegree and ; the case is presented as open here.
Sources & referencesView supporting material
Primary source
Guanwu Liu and Xingxing Yu, “Partitioning digraphs with outdegree at least 4”, arXiv:2006.01116 (2020).
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
Sign in to submit a solution.
No solutions have been posted yet.