Decay of Correlation (Weak Spatial Mixing,WSM) Pr[e∈M|o]e monomerdimer model: L→0∞ M-u regular tree 99…999 boundary condition o:fixing leaf-edges at level l to be occupied/unoccupied by M WSM:Pr[e∈M|]does not depend on o when /∞ WSM always holds+Gibbs measure is always unique [Jerrum,Sinclair'89]:FPRAS for all graphs [Bayati,Gamarnik,Katz,Nair,Tetali'08]:FPTAS for graphs with bounded max-degreeregular tree ` ! 1 boundary condition σ : fixing leaf-edges at level l to be occupied/unoccupied by M Decay of Correlation (Weak Spatial Mixing, WSM) • WSM always holds 㱻 Gibbs measure is always unique • [Jerrum, Sinclair ’89]: FPRAS for all graphs • [Bayati, Gamarnik, Katz, Nair, Tetali ’08]: FPTAS for graphs with bounded max-degree WSM: Pr[e∈M | σ] does not depend on σ when l→∞ monomer-dimer model: Pr[e 2 M | ￾] e M ∼μ