Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
Sinclair, Alistair
Srivastava, Piyush
Thurley, Marc
Centre de Recerca Matemàtica

Publicació: Centre de Recerca Matemàtica 2011
Descripció: 20 p.
Resum: 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.
Drets: 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 Creative Commons
Llengua: Anglès
Col·lecció: Centre de Recerca Matemàtica. Prepublicacions
Col·lecció: Prepublicacions del Centre de Recerca Matemàtica ; 1038
Document: Article ; Prepublicació ; Versió de l'autor
Matèria: Aproximació, Teoria de l' ; Algorismes



20 p, 313.9 KB

El registre apareix a les col·leccions:
Documents de recerca > Prepublicacions

 Registre creat el 2011-10-31, darrera modificació el 2023-02-11



   Favorit i Compartir