Lee–Loh–Sudakov conjecture on judicious bipartitions of digraphs

For a digraph DD, let V(D)V(D) be its vertex set, let mm be its number of arcs, and let e(A,B)e(A,B) denote the number of arcs directed from AA to BB. A bipartition is a decomposition V(D)=V1V2V(D)=V_1\cup V_2. Let dd be an integer satisfying d4d\geq 4.

Lee–Loh–Sudakov conjecture. Every digraph DD with mm arcs and minimum outdegree at least dd admits a bipartition V(D)=V1V2V(D)=V_1\cup V_2 with

min{e(V1,V2),e(V2,V1)}(d12(2d1)+o(1))m.\min\left\{e(V_1,V_2),e(V_2,V_1)\right\}\geq \left(\frac{d-1}{2(2d-1)}+o(1)\right)m.

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 22 and 33; the case d4d\geq 4 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

Never refreshed

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.