Lee–Loh–Sudakov conjecture on judicious bipartitions of digraphs

About 6 years old · traced to

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)=V1∪V2V(D)=V_1\cup V_2. Let dd be an integer satisfying d≥4d\geq 4.

Lee–Loh–Sudakov conjecture. Every digraph DD with mm arcs and minimum outdegree at least dd 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\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 d≥4d\geq 4 is presented as open here.

References

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.