Gibbs measure undirected graph G=(V,E) configuration o∈[g]V w(o) Gibbs distribution:)=HG()- by the chain rule:denoted V={v1,02,...,vn} w(o) w(o) u(σ)】 IIR=1PrX~uG[Xv:Ov:Vj<i:Xv3 =vj marginal probability:()=Pr[X=Xs=] X~HG where ve∈V,x∈[ql,boundary condition o∈[g]s on SCV approximately computing() FPTAS withinμg(c)±in time Poly(m for ZG
Gibbs Measure undirected graph G = (V, E) 2 [q] V configuration Gibbs distribution: by the chain rule: denoted V = {v1, v2,...,vn} where v∈V, x∈[q], boundary condition σ∈[q]S on S⊂V marginal probability: µ v (x) = Pr X⇠µG [Xv = x | XS = ] FPTAS for ZG µ v approximately computing (x) within µ v (x) ± 1 n in time Poly(n) µ() = µG() = w() ZG
Spatial Mixing (Decay of Correlation) marginal distribution at vertex v conditioning on weak spatial mixing(WSM）at rateδ()： o,T∈[g∂R：l呀-呀ITv≤δ(t) boundary conditions R 0 on infinite graphs: WSM uniqueness of infinite- volume Gibbs measure λ≤入c= dd a-a可> WSM of hardcore model on infinite(d+1)-regular tree
Spatial Mixing (Decay of Correlation) R G v t weak spatial mixing (WSM) at rate δ( ): kµ v µ⌧ 8, ⌧ 2 [q] v kT V (t) @R : µ v : marginal distribution at vertex v conditioning on σ boundary conditions on infinite graphs: WSM uniqueness of infinitevolume Gibbs measure µ v c = dd (d1)(d+1) WSM of hardcore model on infinite (d+1)-regular tree ∂R
Spatial Mixing (Decay of Correlation) marginal distribution at vertex v conditioning on weak spatial mixing（WSM)）at rateδ()： o,T∈[goR: lg-Tv≤δ(t) strong spatial mixing(SSM)）at rateδ()： o,T∈[gR,p∈[g]s：lgUp-PlTV≤6(t) SSM marginal prob.(x) is well approximated by the local information
G Spatial Mixing (Decay of Correlation) R v t strong spatial mixing (SSM) at rate δ( ): weak spatial mixing (WSM) at rate δ( ): S kµ v µ⌧ 8, ⌧ 2 [q] v kT V (t) @R : 8, ⌧ 2 [q] @R , 8⇢ 2 [q] S : µ v : marginal distribution at vertex v conditioning on σ SSM µ⇢ v marginal prob. (x) is well approximated by the local information kµ[⇢ v µ⌧[⇢ v kT V (t) ∂R
Tree Recursion hardcore model: pr Prlv is occupied independent set in T T 入Π1(1-p) u()alII 1+入Π1(1-p) (Vi pi=Prlv;is occupied in T RT= PT occupancy ratio: 1-PT d w=中限 i=1
Tree Recursion µ(I) / |I| hardcore model: independent set I in T = Qd i=1(1 pi) 1 + Qd i=1(1 pi) Ti pT = Pr[v is occupied ] v vi pi = Pr[vi is occupied ] in Ti T RT = pT 1 pT occupancy ratio: RT = Y d i=1 1 1 + Ri
Tree Recursion hardcore model: Prlv is occupied R=1-Prv is occupied independent set in G d (I)xλI 爬中 i三1 Prv is occupied] Pr[v2 is occupied o] Prvs is occupiedo] =1-Prvt is occupied R=1-Pri2 is occupied可 fs=1-Prv is occupied可 occupied ☑：unoccupied
R 3 = Pr[v3 is occupied | ] 1 Pr[v3 is occupied | ] R 2 = Pr[v2 is occupied | ] 1 Pr[v2 is occupied | ] R 1 = Pr[v1 is occupied | ] 1 Pr[v1 is occupied | ] R v = Pr[v is occupied | ] 1 Pr[v is occupied | ] R v = Y d i=1 1 1 + R i v v v Tree Recursion µ(I) / |I| hardcore model: independent set I in G v v1 v2 v3 : occupied : unoccupied