Self-Avoiding Walk Tree (Godsil 1981;Weitz 2006) u in G=uroot in T T=TSAW(G,v) E=i4 i=1 SSM in trees: →：n of marginals hold for 2-spin model, monomer-dimer, if cycle closing edge cycle starting edge hypergraph matchings if cycle closing edge cycle starting edge
2 Self-Avoiding Walk Tree 1 2 3 4 5 6 6 5 5 6 4 3 3 5 6 5 6 4 v 1 T = T;)?(G, v) 6 6 6 6 6 G (Godsil 1981; Weitz 2006) if cycle closing edge < cycle starting edge if cycle closing edge > cycle starting edge SSM in trees: • SSM in graphs • efficient approximation of marginals { hold for 2-spin model, monomer-dimer, hypergraph matchings R v = Y d i=1 1 1 + R i µ v µ in G = root in T
SSM in tree hardcore model:i independent set I of weight w(I)= Ipup-pp1≤i(0 lp,-pTl≤() WSM in T “Pinning=Pruning' (model specific) Vo,T Vo,T Goal:WSM in (d+1)-regular tree (= SSM in all trees of max-deg sd+1 Weitz's (d+1)-regular tree is the extremal case for WSM approach: among all trees of max-deg d+1
SSM in tree hardcore model: independent set I of weight w(I) = |I| |p [⇢ T p ⌧[⇢ T | (`) Weitz’s approach: Goal: WSM in (d+1)-regular tree SSM in all trees of max-deg ≤ d +1 ⇣ < c = dd (d1)d+1 ⌘ (d+1)-regular tree is the extremal case for WSM among all trees of max-deg ≤ d +1 T’ ` 8, ⌧ |p T0 p⌧ T0 | (`) “Pinning = Pruning” (model specific) WSM in T’ ` ⇢ T 8, ⌧
hardcore model:i independent set I of weight w(I)= R(=入Π 1 X:vector of nonuniform 1+RF1() T:(d+1)-regular tree Rt(:=sup职( o at level e Rr(X):=inf R(X) σat level e R(A),R():for uniform all Os,all 1s (d+1)-regular tree is the extremal case for WSM among all trees of max-deg sd+1 (through the lens of log-of-ratio) Induction on with hypothesis: |log R()-l1ogR()1≤I|log Ra()-logR()川 Ilog(1+Rt()-log(1+R2()川≤|1og(1+Rt()-log(1+R2()川
all 0s, all 1s hardcore model: independent set I of weight w(I) = |I| (d+1)-regular tree is the extremal case for WSM among all trees of max-deg ≤ d +1 ` = 0 = 0 ~ : vector of nonuniform λ Induction on l with hypothesis: | log R+ ` ( ~ ) log R ` ( ~ )| | log R+ ` () log R ` ()| | log(1 + R+ ` ( ~ )) log(1 + R ` ( ~ ))| | log(1 + R+ ` ()) log(1 + R ` ())| T : (d+1)-regular tree R+ ` ( ~ ) := sup at level ` R T( ~ ) R ` ( ~ ) := inf at level ` R T( ~ ) R+ ` (), R ` () : for uniform λ R± ` ( ~ ) = Y d i=1 1 1 + R⌥ `1( ~ i) (through the lens of log-of-ratio)