Lee, Loh, and Sudakov's conjecture on judicious bipartitions of digraphs

Let DD be a digraph with mm arcs and minimum outdegree at least an integer d2d\geq 2. For a bipartition V(D)=V1V2V(D)=V_1\cup V_2, write e(Vi,Vj)e(V_i,V_j) for the number of arcs directed from ViV_i to VjV_j. Lee, Loh, and Sudakov's conjecture. Every such digraph 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\{e(V_1,V_2),e(V_2,V_1)\}\geq \Big(\frac{d-1}{2(2d-1)}+o(1)\Big)m.

This conjecture addresses Scott's question about the largest constant guaranteeing a balanced directed cut in digraphs with prescribed minimum outdegree. The supplied source does not state whether the conjecture has been resolved.

Sources & referencesView supporting material

Primary source

Jianfeng Hou, Huawen Ma, Xingxing Yu and Xia Zhang, “A bound on judicious bipartitions of directed graphs”, arXiv:1805.05506 (2018).

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.