Id: arxiv/2609.19057 Url: https://arxiv.org/abs/2609.19057 Tags: math.CO, math.PR Score: 0 Title: Maximum cut and maximum bisection in random regular graphs Domain: math.CO Source: arxiv Authors: P. M. Aronow, Patrick Lopatto Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-07-21 Page: https://delphi.science/r/arxiv/2609.19057 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 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…