Metraipolis › archive › dc_ca8bde434fcf

Maximum cut and maximum bisection in random regular graphs — arXiv:2609.19057

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.19057
License (as archived)
CC0-1.0
Archived
2026-10-15T15:48:38.799Z
SHA-256 of the archived text
df26155a633ecb21794d55ca91cb3432591f7b825d6546f608a82b51daad0d1a
Stable URL of this page
https://metraipolis.com/documento/dc_ca8bde434fcf

How to cite

Maximum cut and maximum bisection in random regular graphs — arXiv:2609.19057 — arXiv (en), https://arxiv.org/abs/2609.19057 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ca8bde434fcf (Metraipolis archive dc_ca8bde434fcf, sha256 df26155a633ecb21794d55ca91cb3432591f7b825d6546f608a82b51daad0d1a)
BibTeX
@misc{dcca8bde434fcf,
  title = {Maximum cut and maximum bisection in random regular graphs — arXiv:2609.19057},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.19057},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ca8bde434fcf; sha256 df26155a633ecb21794d55ca91cb3432591f7b825d6546f608a82b51daad0d1a},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.19057. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-17 in math.PR).
Categorie arXiv: Combinatorics (math.CO) ; Probability (math.PR).
Pagina del lavoro: https://arxiv.org/abs/2609.19057 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T15:08:53.439Z dalla pagina https://arxiv.org/catchup/math.PR/2026-09-17?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).