← All problems

10 Lectures and 42 Open Problems — Maximum and minimum bisections on random regular graphs

For a finite graph G=(V,E), a bisection is a partition of V into two parts whose sizes differ by at most one; its size is the number of edges joining the parts. Write MaxBis(G) and MinBis(G) for the largest and smallest such sizes, respectively. The recorded question is whether, for a d-regular graph G on n vertices,

MaxBis⁡(G)+MinBis⁡(G)=d2+o(1)\operatorname{MaxBis}(G)+\operatorname{MinBis}(G)=\frac d2+o(1)

as n grows, for every d. Zdeborová and Boettcher (2010)

This wording does not specify a random-graph law, a mode of convergence, or a normalization of the two bisection sizes. The established random-regular-graph question most closely connected to it concerns the maximum-cut size plus the minimum-bisection size, rather than the sum of the two bisection sizes; these are different formulations. Aronow and Lopatto (2026) Zdeborová and Boettcher (2010)

Background

Maximum cut asks for a partition with as many crossing edges as possible; minimum bisection asks for a balanced partition with as few crossing edges as possible. Both are classical graph-optimization problems, and there is no general identity between their values on an individual graph. Zdeborová and Boettcher proposed in 2010 that, in sparse random regular graphs, the maximum cut is asymptotically the total number of edges minus the minimum-bisection size. Their motivation came from spin-glass arguments, and they also reported numerical evidence. The conjecture concerns maximum cut, not maximum bisection. Zdeborová and Boettcher (2010) Zdeborová and Boettcher (2010)

A separate question, attributed to Bandeira in the later random-graph literature, asks whether maximum cut and maximum bisection have the same expected size up to a sublinear error for fixed degree. This is distinct from the maximum-cut/minimum-bisection conjecture. Keeping these comparisons separate matters when interpreting the recorded formula: replacing either maximum cut by maximum bisection or an edge count by a normalized density changes the mathematical assertion. Aronow and Lopatto (2026)

References

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.