《计算机科学》相关教学资源（参考文献）Spatial mixing and the connective constant - Optimal bounds

wmin2eat optimal bounds Yitong Yin Nanjing University Joint work with: Alistair Sinclair (UC Berkeley) Piyush Srivastava(UC Berkeley) Daniel Stefankovic (Rochester)

Spatial Mixing and the Connective Constant: optimal bounds Yitong Yin Nanjing University Joint work with: Alistair Sinclair (UC Berkeley) Piyush Srivastava (UC Berkeley) Daniel Štefankovič (Rochester)

undirected graph G=(V,E) mtelinofdpof matchings amstnormindpetf matching

undirected graph G = (V,E) approximately counting # of of G matchings {independent sets} almost uniformly sampling a of G matching {independent set}

undirected graph G=(V,E) approximaely countingofof matchings ① computationally equivalent mnifomyamineof matching

undirected graph G = (V,E) approximately counting # of of G matchings {independent sets} almost uniformly sampling a of G matching {independent set} computationally equivalent

undirected graph G=(V,E) monomer-dimer model:set of all matchings M(G) partition function ZA(G)=XIMI M∈M(G)

Z￾(G) = X M2M(G) ￾|M| monomer-dimer model: M(G) undirected graph G = (V,E) set of all matchings partition function

undirected graph G=(V,E) monomer-dimer model:set of all matchings M(G) partition function Z(G)=∑XM M∈M(G) λXMI Gibbs distribution (M)= ZG

Z￾(G) = X M2M(G) ￾|M| monomer-dimer model: M(G) undirected graph G = (V,E) set of all matchings partition function µ(M) = ￾|M| Z￾(G) Gibbs distribution

undirected graph G=V,E) monomer-dimer model:set of all matchings M(G) partition function Z,(G)=∑XM M∈M(G) λXMI Gibbs distribution (M)= Zλ(G) hardcore model: set of all independent sets Z(G) partition function Z(G)=>X四 I∈I(G) λI Gibbs distribution ()= Z,(G)

Z￾(G) = X I2I(G) ￾|I| Z￾(G) = X M2M(G) ￾|M| M(G) I(G) monomer-dimer model: hardcore model: undirected graph G = (V,E) set of all matchings partition function partition function set of all independent sets µ(I) = ￾|I| Z￾(G) µ(M) = ￾|M| Z￾(G) Gibbs distribution Gibbs distribution

Known Results computing the partition function

Known Results computing the partition function

Known Results computing the partition function ● monomer-dimer(matching)

Known Results • monomer-dimer (matching) computing the partition function

Known Results computing the partition function monomer-dimer(matching) FPRAS by MCMC [Jerrum,Sinclair 1989]

Known Results • monomer-dimer (matching) • FPRAS by MCMC [Jerrum, Sinclair 1989] computing the partition function

Known Results computing the partition function monomer-dimer(matching) FPRAS by MCMC [Jerrum,Sinclair 1989] FPTAS for graphs with bounded max-degree [Bayati et al,STOC 2007]

Known Results • monomer-dimer (matching) • FPRAS by MCMC [Jerrum, Sinclair 1989] • FPTAS for graphs with bounded max-degree [Bayati et al, STOC 2007] computing the partition function