Strong Spatial Mixing and Approximating Partition Functions of Two-State Spin Systems without Hard Constrains
| dc.creator | Zhang, Jinshan | |
| dc.date | 2008-12-03 | |
| dc.date | 2009-03-05 | |
| dc.date.accessioned | 2026-07-07T12:48:54Z | |
| dc.date.available | 2026-07-07T12:48:54Z | |
| dc.description | We prove Gibbs distribution of two-state spin systems(also known as binary Markov random fields) without hard constrains on a tree exhibits strong spatial mixing(also known as strong correlation decay), under the assumption that, for arbitrary `external field', the absolute value of `inverse temperature' is small, or the `external field' is uniformly large or small. The first condition on `inverse temperature' is tight if the distribution is restricted to ferromagnetic or antiferromagnetic Ising models. Thanks to Weitz's self-avoiding tree, we extends the result for sparse on average graphs, which generalizes part of the recent work of Mossel and Sly\cite{MS08}, who proved the strong spatial mixing property for ferromagnetic Ising model. Our proof yields a different approach, carefully exploiting the monotonicity of local recursion. To our best knowledge, the second condition of `external field' for strong spatial mixing in this paper is first considered and stated in term of `maximum average degree' and `interaction energy'. As an application, we present an FPTAS for partition functions of two-state spin models without hard constrains under the above assumptions in a general family of graphs including interesting bounded degree graphs. | |
| dc.description | 9 pages | |
| dc.identifier | https://arxiv.org/abs/0812.0754 | |
| dc.identifier | http://arxiv.org/abs/0812.0754 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/222217 | |
| dc.subject | Discrete Mathematics | |
| dc.subject | Graphics | |
| dc.subject | F.2.0 | |
| dc.title | Strong Spatial Mixing and Approximating Partition Functions of Two-State Spin Systems without Hard Constrains | |
| dc.type | text |