MAX -cut and the inhomogeneous Potts spin Glass
From MaRDI portal
Gaussian processes (60G15) Interacting random processes; statistical mechanics type models; percolation theory (60K35) 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) Large-scale problems in mathematical programming (90C06) Combinatorial optimization (90C27)
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
- A mathematical reformulation of Derrida's REM and GREM
- A proof of the block model threshold conjecture
- A Random Graph Model for Power Law Graphs
- 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 mixed p-spin models with vector spins
- Free energy in the Potts spin Glass
- General properties of overlap probability distributions in disordered spin systems. Towards Parisi ultrametricity
- Generating simple random graphs with prescribed degree distribution
- 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?)
- 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 free energy in a multi-species Sherrington-Kirkpatrick model
- The Parisi formula for mixed \(p\)-spin models
- The Parisi ultrametricity conjecture
- The phase transition in inhomogeneous random graphs
- The Sherrington-Kirkpatrick model
- VLSI physical design. From graph partitioning to timing closure
- When are random graphs connected
Cited in
(10)- The overlap gap property in principal submatrix recovery
- Free energy in multi-species mixed \(p\)-spin spherical models
- Extending the Parisi formula along a Hamilton-Jacobi equation
- Free energy of multiple systems of spherical spin glasses with constrained overlaps
- A multi-scale spin-glass mean-field model
- Suboptimality of local algorithms for a class of max-cut problems
- Ultrametricity in spin glasses
- Free energy upper bound for mean-field vector spin glasses
- Parisi formula for balanced Potts spin glass
- On free energy of non-convex multi-species 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)
