MAX \(\kappa\)-cut and the inhomogeneous Potts spin Glass

DOI10.1214/17-AAP1337zbMath1423.90227arXiv1703.03455MaRDI QIDQ1661561

Justin Ko, Aukosh Jagannath, Subhabrata Sen

Publication date: 16 August 2018

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1703.03455

zbMATH Keywords

spin glassesPotts modelinhomogeneous random graphsMAX CUT

Mathematics Subject Classification ID

Gaussian processes (60G15) Large-scale problems in mathematical programming (90C06) Combinatorial optimization (90C27) 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)

Related Items

Free energy in multi-species mixed \(p\)-spin spherical models, A multi-scale spin-glass mean-field model, Extending the Parisi formula along a Hamilton-Jacobi equation, Free energy of multiple systems of spherical spin glasses with constrained overlaps, 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, The overlap gap property in principal submatrix recovery

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimization by Simulated Annealing
• Spin glass models from the point of view of spin distributions
• Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
• Free energy and complexity of spherical bipartite models
• Parisi formula, disorder chaos and fluctuation for the ground state energy in the spherical mixed \(p\)-spin models
• Low temperature asymptotics of spherical mean field spin glasses
• Parisi formula for the ground state energy in the mixed \(p\)-spin model
• Connectedness of certain random graphs
• Generating simple random graphs with prescribed degree distribution
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• When are random graphs connected
• A proof of the block model threshold conjecture
• Free energy in the Potts spin Glass
• Free energy in the mixed \(p\)-spin models with vector spins
• A mathematical reformulation of Derrida's REM and GREM
• Connected components in random graphs with given expected degree sequences
• Broken replica symmetry bounds in the mean field spin glass model
• The Parisi ultrametricity conjecture
• Multi-species mean field spin glasses. Rigorous results
• On the structure of quasi-stationary competing particle systems
• Extremal cuts of sparse random graphs
• The Parisi formula for mixed \(p\)-spin models
• A Random Graph Model for Power Law Graphs
• Statistical mechanics of complex networks
• VLSI Physical Design: From Graph Partitioning to Timing Closure
• Information, Physics, and Computation
• Communities in Networks
• Application of statistical mechanics to NP-complete problems in combinatorial optimisation
• General properties of overlap probability distributions in disordered spin systems. Towards Parisi ultrametricity
• The Sherrington-Kirkpatrick Model
• Community detection thresholds and the weak Ramanujan property
• The phase transition in inhomogeneous random graphs
• On a conditionally Poissonian graph process
• The free energy in a multi-species Sherrington-Kirkpatrick model