Maximum cut and maximum bisection 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)$. Always $\mathrm{MaxBis} \le \mathrm{MaxCut}$, and a random bisection cuts $n(\frac d4 + o(1))$ edges in expectation. Zdeborová and Boettcher conjectured that the three quantities deviate from the average cut by the same amount, and Dembo, Montanari and Sen showed this up to $o_d(\sqrt d)$ as $d \to \infty$.
Problem. Prove or disprove that for every $d \ge 3$, $$\frac1n \mathbb{E}\,\mathrm{MaxCut}(G_d) = \frac1n \mathbb{E}\,\mathrm{MaxBis}(G_d) + o(1).$$
Source: Bandeira, Conjecture 33 of Randomstrasse101, in “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
- 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}
}
Resolution claims
We prove that, for every fixed degree $d$ and a uniformly random simple $d$-regular graph $G_{n,d}$ on an even number $n>d$ of vertices, $$\mathbb{E}\operatorname{MaxCut}(G_{n,d})-\mathbb{E}\operatorname{MaxBis}(G_{n,d})=o(n).$$ In other words, requiring the two sides of a cut to have exactly the same size changes the expected optimal cut by only a sublinear number of edges. We prove this first for the configuration model …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-02 | Open → Solution claimed | The registry's curators | Maximum cut and maximum bisection in random regular graphs v1 recorded from arXiv:2609.19057v1. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00058, "Maximum cut and maximum bisection of random regular graphs", clopen.solutions.