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