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

About 8 years old · traced to

Let DD be a digraph with mm arcs and minimum outdegree at least an integer d≥2d\geq 2. For a bipartition V(D)=V1∪V2V(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)=V1∪V2V(D)=V_1\cup V_2 with

min⁡{e(V1,V2),e(V2,V1)}≥(d−12(2d−1)+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.

References

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.