Minimum and maximum bisections of random regular graphs
Let $G_d$ be a uniformly random $d$-regular graph on $n$ vertices, with $n$ even and $d$ fixed. For a graph on $[n]$ let $\mathrm{cut}(S)$ be the number of edges between $S$ and its complement, and $\mathrm{MinBis} = \min_{|S| = n/2} \mathrm{cut}(S)$, $\mathrm{MaxBis} = \max_{|S| = n/2} \mathrm{cut}(S)$ and $\mathrm{MaxCut} = \max_{S} \mathrm{cut}(S)$. A random bisection cuts $n(\frac d4 + o(1))$ edges in expectation, so $\frac1n \mathbb{E}\,\mathrm{MinBis}(G_d) \le \frac d4 + o(1) \le \frac1n \mathbb{E}\,\mathrm{MaxBis}(G_d) \le \frac1n \mathbb{E}\,\mathrm{MaxCut}(G_d)$. Zdeborová and Boettcher conjectured that the three quantities deviate from the average cut by the same amount. Dembo, Montanari and Sen showed this up to $o_d(\sqrt d)$: divided by $n$, the three are $\frac d4 \pm P_* \sqrt{d/4} + o_d(\sqrt d) + o(1)$, where $P_* \approx 0.76$ is the Parisi constant.
Problem. Prove or disprove that for every $d \ge 3$, $$\frac1n \mathbb{E}\,\mathrm{MinBis}(G_d) + \frac1n \mathbb{E}\,\mathrm{MaxBis}(G_d) = \frac d2 + o(1).$$
Source: Zdeborová and Boettcher (2010). Conjecture 32 of Randomstrasse101, in Bandeira's “Bisections of large random sparse regular graphs” (2026).
The statement is adapted from randomstrasse101.math.ethz.ch, whose text is available under CC BY 4.0.
Classification
- Primary
- PR — Probability
- Secondary
- CO
- Keywords
- graph bisection, maximum cut, random regular graphs, Randomstrasse101, spin glasses
- Literature checked
- Oct. 2, 2026 by clemens-admin
References
@misc{bandeira2026bisections,
author = {Bandeira, Afonso S.},
title = {Bisections of large random sparse regular graphs (problems 32 and 33)},
howpublished = {Randomstrasse101 blog},
year = {2026},
url = {https://randomstrasse101.math.ethz.ch/posts/GraphBisections/}
}
@article{zdeborova2010bisection,
author = {Zdeborov{\'a}, Lenka and Boettcher, Stefan},
title = {A conjecture on the maximum cut and bisection width in random regular graphs},
journal = {Journal of Statistical Mechanics: Theory and Experiment},
volume = {2010},
number = {02},
pages = {P02020},
year = {2010},
doi = {10.1088/1742-5468/2010/02/P02020}
}
@article{dembo2017extremal,
author = {Dembo, Amir and Montanari, Andrea and Sen, Subhabrata},
title = {Extremal cuts of sparse random graphs},
journal = {The Annals of Probability},
volume = {45},
number = {2},
pages = {1190--1217},
year = {2017}
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00046, "Minimum and maximum bisections of random regular graphs", clopen.solutions.