anti-ferromagnetic: By<1 bounded△or△=∞ (B,y,A)lies in the interiors of uniqueness regions of d-regular trees for all ds A. 3 FPTAS for graphs of max-degree A [Sly-Sun'12] [Galanis-Stefankovic-Vigoda'12]: (B,y,A)lies in the interiors of non-uniqueness regions of a-regular trees for some d≤△. NR assuming FPRAS for graphs of max-degree A
anti-ferromagnetic: < 1 ∃ FPTAS for graphs of max-degree Δ (β, γ, λ) lies in the interiors of uniqueness regions of d-regular trees for all d ≤ Δ. ∄ FPRAS for graphs of max-degree Δ (β, γ, λ) lies in the interiors of non-uniqueness regions of d-regular trees for some d ≤ Δ. assuming NP ≠RP [Sly-Sun’12] [Galanis-Stefankovic-Vigoda’12]: bounded Δ or Δ=∞
Uniqueness Condition marginal ±exp(-) (d+1)-regular tree at root d =A(》 t reg. tree 元d=fa(cd) lf(元d)川<1 arbitrary boundary config
Uniqueness Condition (d+1)-regular tree reg. tree t arbitrary boundary config marginal at root ± exp(-t) fd(x) = x + 1 x + d x ˆ d = fd(ˆxd) |f d(ˆxd)| < 1
anti-ferromagnetic:B 1 bounded△or△=o Ju(x)= (》 d<△，f(元d)川<1 3FPTAS for graphs of max-degree A [Sly-Sun'12][Galanis-Stefankovic-Vigoda'12] 3d<△，fa(td)川>1 assuming NP≠RP 肀FPRAS for graphs of max--degree△
anti-ferromagnetic: < 1 ∃ FPTAS for graphs of max-degree Δ ∄ FPRAS for graphs of max-degree Δ assuming NP ≠RP [Sly-Sun’12] [Galanis-Stefankovic-Vigoda’12]: bounded Δ or Δ=∞ d < , |f d(ˆxd)| < 1 d < , |f d(ˆxd)| > 1 fd(x) = x + 1 x + d
Correlation Decay weak spatial mixing (WSM): VoaB,TaB∈{0,1}8B Prlo(v)=0100]P(v)=0TOB] strong spatial mixing (SSM): Pilo(v)=0100,]Pro(v)=0TOB,On] G error exp (-t) exponential correlation decay uniqueness:WSM in reg.tree
Correlation Decay strong spatial mixing (SSM): B B G v B, B {0, 1}B 8Z [(v) = 0 | B] 8Z [(v) = 0 | B] 8Z [(v) = 0 | B, ] 8Z [(v) = 0 | B, ] t error < exp (-t) exponential correlation decay weak spatial mixing (WSM): uniqueness: WSM in reg. tree
Self-Avoiding Walk Tree due to Weitz(2006) G-(V,E T=TSAW(G,U) 3 6 preserve the marginal dist.at v on b bounded degree graphs: SSM> FPTAS
1 Self-Avoiding Walk Tree due to Weitz (2006) 1 2 3 4 5 6 2 4 4 1 4 4 6 5 5 6 4 3 3 5 6 5 6 4 1 G=(V,E) v T = T;)?(G, v) 6 6 6 6 6 preserve the marginal dist. at v SSM FPTAS on bounded degree graphs: