Maximum cut and maximum bisection in random regular graphs

@misc{aronow2026maximum,
  title = {{Maximum cut and maximum bisection in random regular graphs}},
  author = {P. M. Aronow and Patrick Lopatto},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.19057},
  eprint = {2609.19057},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.19057},
}

TY  - UNPB
TI  - Maximum cut and maximum bisection in random regular graphs
AU  - P. M. Aronow
AU  - Patrick Lopatto
PY  - 2026
DA  - 2026/09/01
PB  - arXiv
DO  - 10.48550/arxiv.2609.19057
UR  - https://arxiv.org/abs/2609.19057
AB  - 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, 𝔼MaxCut(G_n,d)−𝔼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 by comparing cuts of each possible cardinality on an n-vertex graph with bisections of a related graph on 2n vertices. An important technical tool is Huang's interpolation theorem (Huang, 2018); to apply it, we establish a structural property of the change in the optimal cut when a single edge is added. This comparison, together with concentration estimates and Huang's convergence theorem for maximum bisection, shows that maximum cut and maximum bisection have the same limiting density. Conditioning the configuration model on being simple then gives the result for uniformly random simple regular graphs.
ER  -