Title: Correlation Decay up to Uniqueness in Spin Systems

Speaker: Yitong Yin, Nanjing Univ.

Time/Date: Friday, Dec 2, 11-12
Location: Room 5510

Abstract:

We give a complete characterization of the two-state
anti-ferromagnetic spin systems which are of exponential correlation
decay. We show that a system is of correlation decay on all graphs
with maximum degree $\Delta$ if and only if the system has a unique
Gibbs measure on all infinite regular trees up to degree $\Delta$,
where $\Delta$ can either be bounded or unbounded. The uniqueness of
Gibbs measure on regular trees is a fundamental property for spin
systems, which has a closed form formulation in terms of the
parameters specifying the system, and is believed to characterize the
approximability of the partition function of a two-state
anti-ferromagnetic spin system.

The exponential correlation decay implies an FPTAS for computing the
partition function of a system on all input graphs of maximum degree
$\Delta$ when the parameters of the system satisfy the uniqueness
condition on infinite regular trees up to degree $\Delta$. In
particular, an FPTAS exists for computing the partition function of a
system on arbitrary input graphs if the uniqueness condition is
satisfied on infinite regular trees of all degrees. This gives a
unified treatment to the algorithmic aspect of the two-state
anti-ferromagnetic spin systems, which covers as special cases all
previous algorithmic results for two-state anti-ferromagnetic spin
systems on general-structure graphs, as well as extends the tractable
region to the uniqueness boundary.