Ground State Properties of the Diluted Sherrington-Kirkpatrick Spin Glass

Abstract

We present a numerical study of ground states of the dilute versions of the Sherrington-Kirkpatrick (SK) mean-field spin glass. In contrast to so-called "sparse" mean-field spin glasses that have been studied widely on random networks of finite (average or regular) degree, the networks studied here are randomly bond-diluted to an overall density $p$, such that the average degree diverges as $\sim pN$ with the system size $N$. Ground-state energies are obtained with high accuracy for random instances over a wide range of fixed $p$. Since this is a NP-hard combinatorial problem, we employ the Extremal Optimization heuristic to that end. We find that the exponent describing the finite-size corrections, $\omega$, varies continuously with $p$, a somewhat surprising result, as one would not expect that gradual bond-dilution would change the $T=0$ universality class of a statistical model. For $p\to 1$, the familiar result of $\omega (p=1)\approx \frac{2}{3}$ for SK is obtained.

arXiv comment5 pages, RevTex, 3 Figs., 1 Tab. Several corrections and refinements. For related information see http://www.physics.emory.edu/faculty/boettcher/

References in corpus (32)

• Weak pairwise correlations imply strongly correlated network states in a neural population
• The Bethe lattice spin glass revisited
• Optimization with Extremal Dynamics
• Nature's Way of Optimizing
• Nature of the Spin Glass State
• Study of the de Almeida-Thouless line using power-law diluted one-dimensional Ising spin glasses
• Energy exponents and corrections to scaling in Ising spin glasses
• Monte Carlo studies of the one-dimensional Ising spin glass with power-law interactions
• Extremal Optimization for Sherrington-Kirkpatrick Spin Glasses
• Stiffness of the Edwards-Anderson Model in all Dimensions
• Extremal Optimization at the Phase Transition of the 3-Coloring Problem
• Interfaces and Lower Critical Dimension in a Spin Glass Model
• The Sherrington-Kirkpatrick model: an overview
• Large Deviations in the Free-Energy of Mean-Field Spin-Glasses
• Finite size corrections in the Sherrington-Kirkpatrick model
• Numerical Results for Ground States of Mean-Field Spin Glasses at low Connectivities
• Low-Temperature Excitations of Dilute Lattice Spin Glasses
• Double Criticality of the Sherrington-Kirkpatrick Model at T=0
• Phase diagram and large deviations in the free-energy of mean-field spin-glasses
• Energy size effects of two-dimensional Ising spin glasses
• Numerical Results for Ground States of Spin Glasses on Bethe Lattices
• Conjecture on the maximum cut and bisection width in random regular graphs
• Support for the value 5/2 for the spin glass lower critical dimension at zero magnetic field
• Simulations of Ground State Fluctuations in Mean-Field Ising Spin Glasses
• Large Deviations of the Free-Energy in Diluted Mean-Field Spin-Glass
• Local field distributions in spin glasses
• Analysis of the Relation between Quadratic Unconstrained Binary Optimization (QUBO) and the Spin Glass Ground-State Problem
• Interface free-energy exponent in the one-dimensional Ising spin glass with long-range interactions in both the droplet and broken replica symmetry regions
• Finite-Size Corrections for Ground States of Edwards-Anderson Spin Glasses
• Numerical Results for Spin Glass Ground States on Bethe Lattices: Gaussian Bonds
• Ground States of the Sherrington-Kirkpatrick Spin Glass with Levy Bonds
• Study of longitudinal fluctuations of the Sherrington-Kirkpatrick model

Cited by in corpus (8)

• Inability of a graph neural network heuristic to outperform greedy algorithms in solving combinatorial optimization problems like Max-Cut
• Classical Annealing of Sherrington-Kirkpatrick Spin Glass Using Suzuki-Kubo Mean-field Ising Dynamics
• The Sherrington-Kirkpatrick model for spin glasses: A new approach for the solution
• Ground state interface exponents of the diluted Sherrington-Kirkpatrick spin glass
• Physics of the Edwards-Anderson Spin Glass in Dimensions $d=3,\dots ,8$ from Heuristic Ground State Optimization
• Ground States of the Mean-Field Spin Glass with 3-Spin Couplings
• Free energy equivalence between mean-field models and nonsparsely diluted mean-field models
• Mean-field theory of vector spin models on networks with arbitrary degree distributions