Computer Science – Data Structures and Algorithms
Scientific paper
2011-11-30
Computer Science
Data Structures and Algorithms
27 pages, submitted for publication
Scientific paper
We give a complete characterization of the two-state anti-ferromagnetic spin systems which are of strong spatial mixing on general graphs. We show that a two-state anti-ferromagnetic spin system is of strong spatial mixing on all graphs of maximum degree at most \Delta if and only if the system has a unique Gibbs measure on infinite regular trees of degree up to \Delta, where \Delta can be either bounded or unbounded. As a consequence, there exists an FPTAS for the partition function of a two-state anti-ferromagnetic spin system on graphs of maximum degree at most \Delta when the uniqueness condition is satisfied on infinite regular trees of degree up to \Delta. In particular, an FPTAS exists for arbitrary graphs if the uniqueness is satisfied on all infinite regular trees. This covers as special cases all previous algorithmic results for two-state anti-ferromagnetic systems on general-structure graphs. Combining with the FPRAS for two-state ferromagnetic spin systems of Jerrum-Sinclair and Goldberg-Jerrum-Paterson, and the very recent hardness results of Sly-Sun and independently of Galanis-Stefankovic-Vigoda, this gives a complete classification, except at the phase transition boundary, of the approximability of all two-state spin systems, on either degree-bounded families of graphs or family of all graphs.
Li Liang
Lu Pinyan
Yin Yitong
No associations
LandOfFree
Correlation Decay up to Uniqueness in Spin Systems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Correlation Decay up to Uniqueness in Spin Systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Correlation Decay up to Uniqueness in Spin Systems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-7286