Search

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 ∼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 an NP-hard combinatorial problem, we employ the extremal optimization heuristic to that end. We find that the exponent describing the finite-size corrections ω 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→1, the familiar result of ω(p=1)≈2/3 for the SK model is obtained.

A comprehensive description in all dimensions is provided for the scaling exponent y of low-energy excitations in the Ising spin glass introduced by Edwards and Anderson. A combination of extensive numerical as well as theoretical results suggest that its lower critical dimension is exactly dl=5/2. Such a result would be an essential feature of any complete theory of low-temperature spin glass order and imposes a constraint that may help to distinguish between theories.

A sequence of bursts observed in an intermittent time series may be caused by a single avalanche, even though these bursts appear as distinct events when noise and/or instrument resolution impose a detection threshold. In the Bak-Tang-Wiesenfeld sandpile, the statistics of quiet times between bursts switches from Poissonian to scale invariant on raising the threshold for detecting instantaneous activity, since each zero-threshold avalanche breaks into a hierarchy of correlated bursts. Calibrating the model with the time resolution of GOES data, qualitative agreement with the interoccurrence time statistics of solar flares at different intensity thresholds is found.

We explore a new general-purpose heuristic for finding high-quality solutions to hard discrete optimization problems. The method, called extremal optimization, is inspired by self-organized criticality, a concept introduced to describe emergent complexity in physical systems. Extremal optimization successively updates extremely undesirable variables of a single suboptimal solution, assigning them new, random values. Large fluctuations ensue, efficiently exploring many local optima. We use extremal optimization to elucidate the phase transition in the 3-coloring problem, and we provide independent confirmation of previously reported extrapolations for the ground-state energy of +/-J spin glasses in d = 3 and 4.

Numerical results are presented indicating d(c) = 4 as the upper critical dimension for the Bak-Sneppen evolution model. This finding agrees with previous theoretical arguments, but contradicts a recent Letter [Phys. Rev. Lett. 80, 5746 (1998)] that placed d(c) as high as d = 8. In particular, we find that avalanches are compact for all dimensions d< or =4 and are fractal for d>4. Under those conditions, scaling arguments predict a d(c) = 4, where hyperscaling relations hold for d< or =4. Other properties of avalanches, studied for 1< or =d< or =6, corroborate this result. To this end, an improved numerical algorithm is presented that is based on the equivalent branching process.