To cite this record: http://ddd.uab.cat/record/81059
Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
Sinclair, Alistair
Srivastava, Piyush
Thurley, Marc
Centre de Recerca Matemàtica

Imprint: Centre de Recerca Matemàtica 2011
Description: 20 p.
Series: Prepublicacions del Centre de Recerca Matemàtica ; 1038
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.
Rights: 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
Language: Anglès.
Document: preprint
Subject: Aproximació, Teoria de l' ; Algorismes

Adreça alternativa: http://hdl.handle.net/2072/171420


20 p, 313.9 KB

The record appears in these collections:
Research literature > Preprints

 Record created 2011-10-31, last modified 2014-06-07



   Favorit i Compartir
QR image