{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-21","reactions":{}}