Extremal Cuts of Sparse Random Graphs

Abstract

For Erdős-Rényi random graphs with average degree $\gamma$, and uniformly random $\gamma$-regular graph on $n$ vertices, we prove that with high probability the size of both the Max-Cut and maximum bisection are $n(\frac{\gamma }{4}+{\mathsf{P}}_{\ast }\sqrt{\frac{\gamma }{4}}+o(\sqrt{\gamma }))+o(n)$ while the size of the minimum bisection is $n(\frac{\gamma }{4}-{\mathsf{P}}_{\ast }\sqrt{\frac{\gamma }{4}}+o(\sqrt{\gamma }))+o(n)$. Our derivation relates the free energy of the anti-ferromagnetic Ising model on such graphs to that of the Sherrington-Kirkpatrick model, with ${\mathsf{P}}_{\ast }\approx 0.7632$ standing for the ground state energy of the latter, expressed analytically via Parisi's formula.

19 pages

References in corpus (3)

• Broken Replica Symmetry Bounds in the Mean Field Spin Glass Model
• The high temperature region of the Viana-Bray diluted spin glass model
• A Dynamic Programming Approach to the Parisi Functional

Cited by in corpus (46)

• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Combinatorial Optimization with Physics-Inspired Graph Neural Networks
• Suboptimality of local algorithms for a class of max-cut problems
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples
• Benchmarking quantum co-processors in an application-centric, hardware-agnostic and scalable way
• The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model
• Parameter Setting in Quantum Approximate Optimization of Weighted Problems
• QAOAKit: A Toolkit for Reproducible Study, Application, and Verification of the QAOA
• Faster quantum and classical SDP approximations for quadratic binary optimization
• Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models
• Bounds on approximating Max $k$XOR with quantum and classical local algorithms
• Inability of a graph neural network heuristic to outperform greedy algorithms in solving combinatorial optimization problems like Max-Cut
• A connection between MAX $\kappa$-CUT and the inhomogeneous Potts spin glass in the large degree limit
• Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs
• Zero-temperature dynamics in the dilute Curie-Weiss model
• Scalable Connectivity for Ising Machines: Dense to Sparse
• Optimization on Sparse Random Hypergraphs and Spin Glasses
• (Dis)assortative Partitions on Random Regular Graphs
• A Tight Degree 4 Sum-of-Squares Lower Bound for the Sherrington-Kirkpatrick Hamiltonian
• Graph Neural Networks for Maximum Constraint Satisfaction
• Analyzing the quantum approximate optimization algorithm: ansätze, symmetries, and Lie algebras
• Bounds on the ground state energy of quantum $p$-spin Hamiltonians
• The SK model is infinite step replica symmetry breaking at zero temperature
• Kawasaki dynamics beyond the uniqueness threshold
• Lifting Sum-of-Squares Lower Bounds: Degree-$2$ to Degree-$4$
• Parisi formula for the ground state energy in the mixed p-spin model
• Combinatorial NLTS From the Overlap Gap Property
• An explicit vector algorithm for high-girth MaxCut
• On the unbalanced cut problem and the generalized Sherrington-Kirkpatrick model
• On the $K$-sat model with large number of clauses
• Positivity-preserving extensions of sum-of-squares pseudomoments over the hypercube
• The minimum bisection in the planted bisection model
• The Overlap Gap Property limits limit swapping in the QAOA
• Limits of Short-Time Evolution of Local Hamiltonians
• Breaking of 1RSB in random MAX-NAE-SAT
• Local approximation of the Maximum Cut in regular graphs
• Metastability and maximal-entropy joinings of Gibbs measures on finitely-generated groups
• Experimental performance of graph neural networks on random instances of max-cut
• Disorder chaos in some diluted spin glass models
• Improving the Quantum Approximate Optimization Algorithm with postselection
• Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm
• Vector Colorings of Random, Ramanujan, and Large-Girth Irregular Graphs
• Modularity of regular and treelike graphs
• Maximum chordal subgraphs of random graphs
• Max-Cut in Degenerate $H$-Free Graphs
• On MAXCUT in strictly supercritical random graphs, and coloring of random graphs and random tournaments