Lee, Loh and Sudakov's directed-cut bisection conjecture

About 8 years old · traced to

Let DD) be a digraph with mm arcs, and for a bipartition V(D)=V1∪V2V(D)=V_1\cup V_2, let e(Vi,Vj)e(V_i,V_j) denote the number of arcs directed from ViV_i to VjV_j. Let d≥3d\geq 3 be a positive integer.

Lee, Loh and Sudakov's conjecture. Every digraph DD with minimum outdegree at least d+1d+1 admits a bipartition V(D)=V1∪V2V(D)=V_1\cup V_2 such that

min⁡{e(V1,V2),e(V2,V1)}≥(d2(2d+1)+o(1))m.\min\left\{e(V_1,V_2),e(V_2,V_1)\right\}\geq \left(\frac{d}{2(2d+1)}+o(1)\right)m.

This conjecture extends the known asymptotic cases c2=1/6+o(1)c_2=1/6+o(1) and c3=1/5+o(1)c_3=1/5+o(1) for the largest guaranteed proportion of arcs in both directions of a directed cut. The general case remains open.

References

Primary source

Guanwu Liu, Jie Ma and Chunlei Zu, “Optimal bisections of directed graphs”, arXiv:2302.04050 (2023).

Additional references

2 papers in this index state this conjecture (2018–2023). The statement above is taken from the most recent of them; the others are arXiv:1805.05506.

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.