Counting with Bounded Treewidth Yitong Yin Nanjing University Joint work with Chihao Zhang (SJTU→)
Counting with Bounded Treewidth Yitong Yin Nanjing University Joint work with Chihao Zhang (SJTU ⟶ ?)
Spin Systems vertices are variables (domain [gl) graph G=(V,E) edge are constraints: A(u,v) Ve=(u,y)∈E Ae:[gl×[gl→C configuration o∈[g]'Y partition function: Z=∑ΠAe(ou,o) o∈[g]Ve=(u,v)eE
Spin Systems vertices are variables (domain [q]) edge are constraints: graph G=(V,E) configuration partition function: 2 [q] V A(u,v) Z = X 2[q]V Y e=(u,v)2E Ae(u, v) Ae : [q] ⇥ [q] ! C ∀e=(u,v) ∈ E
Holant Problem edges are variables (domain [gl) graph G=(V,E) vertices are constraints (signatures) nu∈V,fu:[]deg(w)C configuration o∈[glE holant=If(oE()） o∈[g]Ev∈V E(v)=(e1,.,ed) incident edges of v q"configurations where m=lEl
Holant Problem edges are variables (domain [q]) vertices are constraints (signatures) fv [q] E configuration holant = X 2[q]E Y v2V fv |E(v) 8v 2 V, fv : [q] deg(v) ! C E(v) = (e1, ... , ed) incident edges of v qm configurations where m=|E| graph G=(V,E)
incidence graph B(V,E,F) graph G=(V,E) 2 EQ 3 Ae E o∈[glV where w(o)=ΠAe(ou,0) e=(u,v)∈E B0z0= 1 c1=··=xd otherwise Z=∑w(a) holant=∑[f(alr) o∈[qV o∈[glFv∈VUE
1 2 3 4 5 a b c d e f incidence graph B(V,E,F) V E 8 2 [q] V w() = Y e=(u,v)2E Ae(u, v) F EQ Ae EQ(x1,...,xd) = ( 1 x1 = ··· = xd 0 otherwise where Z = X 2[q]V w() holant = X 2[q]F Y v2V [E fv |F (v) graph G=(V,E) 1 2 3 4 5 a b c d e f
9=2 graph G=(V,E) Boolean symmetric f:10,1dC f=[6,f,,jf闭 where fi=x)for∑xi=i counting matchings: at every vertex vev, =[1,1,0,0.,0] the at-most-one function holant ∑Π1,1,0，.…，0(oE@） o∈{0,1}Ev∈V
f = [f0, f1 ,..., fd] where fi = f(x) for Σjxj = i f : {0, 1} Boolean symmetric d ! C at every vertex v∈V, fv = [1, 1, 0, 0..., 0] counting matchings: the at-most-one function q=2 holant = X 2{0,1}E Y v2V [1, 1, 0,..., 0] |E(v) graph G=(V,E) fv