Title:
|
Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
|
Author:
|
Sinclair, Alistair; Srivastava, Piyush; Thurley, Marc; Universitat Autònoma de Barcelona. Centre de Recerca Matemàtica
|
Abstract:
|
In a seminal paper [10], Weitz gave a deterministic fully polynomial approximation scheme for counting exponentially weighted independent sets (which is the same as approximating the partition function of the hard-core model from statistical physics) in graphs of degree at most d, up to the critical activity for the uniqueness of the Gibbs measure on the in nite d-regular tree. More recently Sly [8] (see also [1]) showed that this is optimal in the sense that if there is an FPRAS for the hard-core partition function on graphs of maximum degree d for activities larger than the critical activity on the in nite d-regular tree then NP = RP. In this paper we extend Weitz's approach to derive a deterministic fully polynomial approximation scheme for the partition function of general two-state anti-ferromagnetic spin systems on graphs of maximum degree d, up to the corresponding critical point on the d-regular tree. The main ingredient of our result is a proof that for two-state anti-ferromagnetic spin systems on the d-regular tree, weak spatial mixing implies strong spatial mixing. This in turn uses a message-decay argument which extends a similar approach proposed recently for the hard-core model by Restrepo et al [7] to the case of general two-state anti-ferromagnetic spin systems. |
Subject(s):
|
-Aproximació, Teoria de l' -Algorismes |
Rights:
|
open access
Aquest document està subjecte a una llicència d'ús de Creative Commons, amb la qual es permet copiar, distribuir i comunicar públicament l'obra sempre que se'n citin l'autor original, la universitat i el centre i no se'n faci cap ús comercial ni obra derivada, tal com queda estipulat en la llicència d'ús
https://creativecommons.org/licenses/by-nc-nd/2.5/ |
Document type:
|
Article Prepublicació |
Published by:
|
Centre de Recerca Matemàtica
|
Share:
|
|
Uri:
|
https://ddd.uab.cat/record/81059
|