اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدSome spin glass ideas applied to the clique problem
88
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
In this paper we introduce a new algorithm to study some NP-complete problems. This algorithm is a Markov Chain Monte Carlo (MCMC) inspired by the cavity method developed in the study of spin glass. We will focus on the maximum clique problem and we will compare this new algorithm with several standard algorithms on some DIMACS benchmark graphs and on random graphs. The performances of the new algorithm are quite surprising. Our effort in this paper is to be clear as well to those readers who are not in the field.
قيم البحث
اقرأ أيضاً
Magnetic ordering at low temperature for Ising ferromagnets manifests itself within the associated Fortuin-Kasteleyn (FK) random cluster representation as the occurrence of a single positive density percolating network. In this paper we investigate t
he percolation signature for Ising spin glass ordering -- both in short-range (EA) and infinite-range (SK) models -- within a two-replica FK representation and also within the different Chayes-Machta-Redner two-replica graphical representation. Based on numerical studies of the $pm J$ EA model in three dimensions and on rigorous results for the SK model, we conclude that the spin glass transition corresponds to the appearance of {it two} percolating clusters of {it unequal} densities.
URh_2Ge_2 occupies an extraordinary position among the heavy-electron 122-compounds, by exhibiting a previously unidentified form of magnetic correlations at low temperatures, instead of the usual antiferromagnetism. Here we present new results of ac
and dc susceptibilities, specific heat and neutron diffraction on single-crystalline as-grown URh_2Ge_2. These data clearly indicate that crystallographic disorder on a local scale produces spin glass behavior in the sample. We therefore conclude that URh_2Ge_2 is a 3D Ising-like, random-bond, heavy-fermion spin glass.
We study in detail the quantum Sherrington-Kirkpatrick (SK) model, i.e. the infinite-range Ising spin glass in a transverse field, by solving numerically the effective one-dimensional model that the quantum SK model can be mapped to in the thermodyna
mic limit. We find that the replica symmetric (RS) solution is unstable down to zero temperature, in contrast to some previous claims, and so there is not only a line of transitions in the (longitudinal) field-temperature plane (the de Almeida-Thouless, AT, line) where replica symmetry is broken, but also a quantum de Almeida-Thouless (QuAT) line in the transverse field-longitudinal field plane at $T = 0$. If the QuAT line also occurs in models with short-range interactions its presence might affect the performance of quantum annealers when solving spin glass-type problems with a bias (i.e. magnetic field).
The chiral spin-glass Potts system with q=3 states is studied in d=2 and 3 spatial dimensions by renormalization-group theory and the global phase diagrams are calculated in temperature, chirality concentration p, and chirality-breaking concentration
c, with determination of phase chaos and phase-boundary chaos. In d=3, the system has ferromagnetic, left-chiral, right-chiral, chiral spin-glass, and disordered phases. The phase boundaries to the ferromagnetic, left- and right-chiral phases show, differently, an unusual, fibrous patchwork (microreentrances) of all four (ferromagnetic, left-chiral, right-chiral, chiral spin-glass) ordered ordered phases, especially in the multicritical region. The chaotic behavior of the interactions, under scale change, are determined in the chiral spin-glass phase and on the boundary between the chiral spin-glass and disordered phases, showing Lyapunov exponents in magnitudes reversed from the usual ferromagnetic-antiferromagnetic spin-glass systems. At low temperatures, the boundaries of the left- and right-chiral phases become thresholded in p and c. In the d=2, the chiral spin-glass system does not have a spin-glass phase, consistently with the lower-critical dimension of ferromagnetic-antiferromagnetic spin glasses. The left- and right-chirally ordered phases show reentrance in chirality concentration p.
We develop a novel method based in the sparse random graph to account the interplay between geometric frustration and disorder in cluster magnetism. Our theory allows to introduce the cluster network connectivity as a controllable parameter. Two type
s of inner cluster geometry are considered: triangular and tetrahedral. The theory was developed for a general, non-uniform intra-cluster interactions, but in the present paper the results presented correspond to uniform, anti-ferromagnetic (AF) intra-clusters interactions $J_{0}/J$. The clusters are represented by nodes on a finite connectivity random graph, and the inter-cluster interactions are random Gaussian distributed. The graph realizations are treated in replica theory using the formalism of order parameter functions, which allows to calculate the distribution of local fields and, as a consequence, the relevant observable. In the case of triangular cluster geometry, there is the onset of a classical Spin Liquid state at a temperature $T^{*}/J$ and then, a Cluster Spin Glass (CSG) phase at a temperature $T_{f}/J$. The CSG ground state is robust even for very weak disorder or large negative $J_{0}/J$. These results does not depend on the network connectivity. Nevertheless, variations in the connectivity strongly affect the level of frustration $f_{p}=-Theta_{CW}/T_{f}$ for large $J_{0}/J$. In contrast, for the non-frustrated tetrahedral cluster geometry, the CSG ground state is suppressed for weak disorder or large negative $J_{0}/J$. The CSG boundary phase presents a re-entrance which is dependent on the network connectivity.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
