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

From papers

Let DD) be a digraph with mm arcs, and for a bipartition V(D)=V1V2V(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 d3d\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)=V1V2V(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.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

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.

Solutions 0

No solutions have been posted yet.