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