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] spatial hardcore(independent set) mixing FPRAS for counting independent sets (=1)of graphs with max-degree <4 [Dyer,Greenhill 2000;Vigoda 2001] FPTAS for graphs with max-degree d when A<c(d-1) [Weitz,STOC 2006] dd uniqueness threshold:Xe(d)=d-1)+ inapproxamable if >c(d-1)[Sly,FOCS 2010;Sly,Sun, FOCS 20121
Known Results • monomer-dimer (matching) • FPRAS by MCMC [Jerrum, Sinclair 1989] • FPTAS for graphs with bounded max-degree [Bayati et al, STOC 2007] • hardcore (independent set) • FPRAS for counting independent sets (λ=1) of graphs with max-degree ≤4 [Dyer, Greenhill 2000; Vigoda 2001] • FPTAS for graphs with max-degree d when λ<λc(d-1) [Weitz, STOC 2006] • inapproxamable if λ>λc(d-1) [Sly, FOCS 2010; Sly, Sun, FOCS 2012] uniqueness threshold: spatial mixing computing the partition function c(d) = dd (d 1)d+1
Connective Constants [Madras,Slade 1996] N(v,e):number of paths of length starting from v
Connective Constants N(v, `) : number of paths of length l starting from v [Madras, Slade 1996]
Connective Constants [Madras,Slade 1996] N(v,e):number of paths of length l starting from v for an infinite graph G: connective constant A()N(v) v∈V
Connective Constants (G) = sup v2V lim sup `!1 N(v, `) 1/` N(v, `) : number of paths of length l starting from v for an infinite graph G: connective constant [Madras, Slade 1996]
Connective Constants [Madras,Slade 1996] N(v,e):number of paths of length starting fromv for an infinite graph G: connective constant A(G)=sup lim sup N(v,e)1/e v∈V 0→∞ can be similarly defined for a family g of finite graphs
Connective Constants (G) = sup v2V lim sup `!1 N(v, `) 1/` N(v, `) : number of paths of length l starting from v for an infinite graph G: connective constant can be similarly defined for a family G of finite graphs [Madras, Slade 1996]
Connective Constants [Madras,Slade 1996] N(v,e):number of paths of length l starting from v for an infinite graph G: connective constant A(G)=sup lim sup N(v,e)1/e u∈V 0→∞ can be similarly defined for a family g of finite graphs the connective constant represents the average growth rate of number of paths from a vertex
Connective Constants (G) = sup v2V lim sup `!1 N(v, `) 1/` N(v, `) : number of paths of length l starting from v for an infinite graph G: connective constant can be similarly defined for a family G of finite graphs [Madras, Slade 1996] the connective constant represents the average growth rate of number of paths from a vertex