(An algorithmic perspective to the) Decay of Correlation in Spin Systems Yitong Yin Nanjing University
(An algorithmic perspective to the) Decay of Correlation in Spin Systems Yitong Yin Nanjing University
Decay of Correlation hardcore model: Pr[v∈I|o] H(I)xIII a+I)-ur。o →∝ ○-○-○- o:fixing leaves to be occupied/unoccupied by I Decay of correlation:Pr[velI o]does not depend on o when d if入≤入。=(d-1)a+西 counting total weights n of all I.S.in graphs with max-degree <d+1 ●λ<λc→FPTAS[Weitz06] ●λ>λc→no FPRAS unless NP=RP [Sly10][Galanis Stefankovie Vigoda 12][Sly Sun 12]
regular tree ` ! 1 v σ: fixing leaves to be occupied/unoccupied by I Pr[v 2 I | ] Decay of Correlation hardcore model: • λ < λc 㱺 FPTAS • λ > λc 㱺 no FPRAS unless NP=RP Decay of correlation: Pr[v∈I | σ] does not depend on σ when l→∞ random independent set I iff counting total weights λ|I| of all I.S. in graphs with max-degree ≤ d+1 [Sly10] [Galanis Štefankovič Vigoda 12] [Sly Sun 12] [Weitz 06] (d+1)-
Spin System undirected graph G=(V,E) fixed integer g≥2 configuration o∈[glY weight:w(o)=A(ou,)b(o) {u,w}∈E u∈V A:[ql×[q→R≥o symmetric gxy matrix (symmetric binary constraint) b:[q→R>0 g-vector (unary constraint) partition function: zc=∑w(o) o∈[glV Gibbs distribution: c(o)= w(o) ZG
Spin System undirected graph G = (V, E) fixed integer q ≥ 2 2 [q] V configuration w() = Y {u,v}2E A(u, v) Y v2V weight: b(v) A : [q] ⇥ [q] ! R0 b : [q] ! R0 symmetric q×q matrix q-vector (symmetric binary constraint) partition function: ZG = X 2[q]V w() Gibbs distribution: µG() = w() ZG (unary constraint)
undirected graph G=(V,E) fixed integer g≥2 configuration o∈[g]Y weight:w(o)=A(ou,)b() {u,v}∈E u∈V 2-spin model:q=2,o{0,1} 4- edge activities 6= -9 external field hardcore model:B=0,y=1 ZG= ∑ λ川 I:independent sets in G ·Ising model:B=y multi-spin model:general g=2 ·Potts model: A= 81 ·q-coloring: B=0 1 b= 1
• 2-spin model: q =2, • hardcore model: β=0, γ=1 • Ising model: β = γ • multi-spin model: general q ≥ 2 • Potts model: • q-coloring: β=0 undirected graph G = (V, E) fixed integer q ≥ 2 2 [q] V configuration w() = Y {u,v}2E A(u, v) Y v2V weight: b(v) 2 {0, 1}V A = A00 A01 A10 A11 = 1 1 b = b0 b1 = 1 edge activities external field 1 1 2 6 6 6 4 ... 3 7 7 7 A = 5 2 6 4 1 . . . 1 3 7 b = 5 ZG = X I: independent sets in G |I|
Models ●spin systems: Ising model,Potts model,g-coloring ●hardcore model generalization hypergraph matchings ● nonomer-dimer一 ZG= ∑ AIMI (NOT a spin system) M:matchings in G Holant problem defined by the (weighted-)EQ,the At-Most-One constraint,and any binary constraints The recursion of marginal probabilities is the same as a recursion on the tree of self-avoiding walks. (hopefully) correlation decay tractability of on trees approximate counting
Models • spin systems: • Ising model, Potts model, q-coloring • hardcore model • monomer-dimer • Holant problem defined by the (weighted-)EQ, the At-Most-One constraint, and any binary constraints • The recursion of marginal probabilities is the same as a recursion on the tree of self-avoiding walks. (NOT a spin system) hypergraph matchings generalization correlation decay on trees tractability of approximate counting (hopefully) ZG = X M: matchings in G |M|