Conjecture on the maximum cut and bisection width in random regular graphs

Abstract

Asymptotic properties of random regular graphs are object of extensive study in mathematics. In this note we argue, based on theory of spin glasses, that in random regular graphs the maximum cut size asymptotically equals the number of edges in the graph minus the minimum bisection size. Maximum cut and minimal bisection are two famous NP-complete problems with no known general relation between them, hence our conjecture is a surprising property of random regular graphs. We further support the conjecture with numerical simulations. A rigorous proof of this relation is obviously a challenge.

12 pages

References in corpus (1)

• Potts Glass on Random Graphs

Cited by in corpus (20)

• Statistical physics of inference: Thresholds and algorithms
• Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
• The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs
• Extremal Cuts of Sparse Random Graphs
• Simulations of Ground State Fluctuations in Mean-Field Ising Spin Glasses
• Inability of a graph neural network heuristic to outperform greedy algorithms in solving combinatorial optimization problems like Max-Cut
• Belief propagation for graph partitioning
• Ground State Properties of the Diluted Sherrington-Kirkpatrick Spin Glass
• Random-field p-spin glass model on regular random graphs
• (Dis)assortative Partitions on Random Regular Graphs
• Backtracking Dynamical Cavity Method
• Maximum edge-cuts in cubic graphs with large girth and in random cubic graphs
• Numerical Results for Spin Glass Ground States on Bethe Lattices: Gaussian Bonds
• Circular Coloring of Random Graphs: Statistical Physics Investigation
• Ground States of the Sherrington-Kirkpatrick Spin Glass with Levy Bonds
• Convergence of Maximum Bisection Ratio of Sparse Random Graphs
• Physics of the Edwards-Anderson Spin Glass in Dimensions $d=3,\dots ,8$ from Heuristic Ground State Optimization
• Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm
• The Random Quadratic Assignment Problem
• Dynamical Cavity Method for Hypergraphs and its Application to Quenches in the k-XOR-SAT Problem