MAX -cut and the inhomogeneous Potts spin Glass
From MaRDI portal
Gaussian processes (60G15) Large-scale problems in mathematical programming (90C06) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Combinatorial optimization (90C27) Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics (82B44) Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) (82D30)
Abstract: We study the asymptotic behavior of the Max -cut on a family of sparse, inhomogeneous random graphs. In the large degree limit, the leading term is a variational problem, involving the ground state of a constrained inhomogeneous Potts spin glass. We derive a Parisi type formula for the free energy of this model, with possible constraints on the proportions, and derive the limiting ground state energy by a suitable zero temperature limit.
Recommendations
Cites work
- scientific article; zbMATH DE number 1273988 (Why is no real title available?)
- scientific article; zbMATH DE number 2046059 (Why is no real title available?)
- scientific article; zbMATH DE number 747040 (Why is no real title available?)
- A Random Graph Model for Power Law Graphs
- A mathematical reformulation of Derrida's REM and GREM
- A proof of the block model threshold conjecture
- Application of statistical mechanics to NP-complete problems in combinatorial optimisation
- Broken replica symmetry bounds in the mean field spin glass model
- Communities in Networks
- Community detection thresholds and the weak Ramanujan property
- Concentration inequalities. A nonasymptotic theory of independence
- Connected components in random graphs with given expected degree sequences
- Connectedness of certain random graphs
- Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
- Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
- Extremal cuts of sparse random graphs
- Free energy and complexity of spherical bipartite models
- Free energy in the Potts spin Glass
- Free energy in the mixed \(p\)-spin models with vector spins
- General properties of overlap probability distributions in disordered spin systems. Towards Parisi ultrametricity
- Generating simple random graphs with prescribed degree distribution
- Information, Physics, and Computation
- Low temperature asymptotics of spherical mean field spin glasses
- Multi-species mean field spin glasses. Rigorous results
- On a conditionally Poissonian graph process
- On the structure of quasi-stationary competing particle systems
- Optimization by simulated annealing
- Parisi formula for the ground state energy in the mixed \(p\)-spin model
- Parisi formula, disorder chaos and fluctuation for the ground state energy in the spherical mixed \(p\)-spin models
- Social and economic networks.
- Spin glass models from the point of view of spin distributions
- Statistical mechanics of complex networks
- The Parisi formula for mixed \(p\)-spin models
- The Parisi ultrametricity conjecture
- The Sherrington-Kirkpatrick model
- The free energy in a multi-species Sherrington-Kirkpatrick model
- The phase transition in inhomogeneous random graphs
- VLSI physical design. From graph partitioning to timing closure
- When are random graphs connected
Cited in
(9)- Free energy upper bound for mean-field vector spin glasses
- Suboptimality of local algorithms for a class of max-cut problems
- A multi-scale spin-glass mean-field model
- Extending the Parisi formula along a Hamilton-Jacobi equation
- Free energy in multi-species mixed \(p\)-spin spherical models
- Free energy of multiple systems of spherical spin glasses with constrained overlaps
- Parisi formula for balanced Potts spin glass
- The overlap gap property in principal submatrix recovery
- Ultrametricity in spin glasses
This page was built for publication: MAX \(\kappa\)-cut and the inhomogeneous Potts spin Glass
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1661561)
