Phase Transition of Hypergraph Matchings Yitong Yin Nanjing University Joint work with:Jinman Zhao (Nanjing Univ./U Wisconsin)
Phase Transition of Hypergraph Matchings Joint work with: Jinman Zhao (Nanjing Univ. / U Wisconsin) Yitong Yin Nanjing University
hardcore model monomer-dimer model undirected graph G=V,E) activity入 configurations: independent sets matchings M weight: w(D=入M w(M)=入M partition function: Z=1:independent sets in GW(D =EM:matchingsin G W(M) Gibbs distribution: u(D)=w(D/Z u(M)=w(M)/Z approximate counting: FPTAS/FPRAS for Z sampling:sampling from u within TV-distance s in time poly(n,log1/8)
hardcore model monomer-dimer model configurations: independent sets I matchings M weight: w(I) = λ|I| w(M) = λ|M| partition function: Z = ΣI:independent sets in G w(I) Z = ΣM:matchings in G w(M) Gibbs distribution: μ(I) = w(I) / Z μ(M) = w(M) / Z approximate counting: sampling: FPTAS/FPRAS for Z sampling from μ within TV-distance ε in time poly(n, log1/ε) G = (V,E) undirected graph λ λ λ λ λ λ λ activity λ λ λ
Decay of Correlation (Weak Spatial Mixing,WSM) Pr[v∈I|o] hardcore model: I-u →∞ (d+1)-regular tree ---0 boundary condition o:fixing leaves at level l to be occupied/unoccupied by I WSM:Pr[lv∈I|o]does not depend on o when l-→o uniqueness threshold:Xc= (d-1)d+1) ●入≤入c台VSM holds on(d+l)-regular tree台Gibbs measure is unique ·Veitz'06]:λ<λc→FPTAS for graphs with max-degree≤dtl [Galanis,Stefankovic,Vigoda'12;Sly,Sun'12]:>e inapproximable unless NP=RP
(d+1)-regular tree ` ! 1 v boundary condition σ : fixing leaves at level l to be occupied/unoccupied by I Pr[v 2 I | ] Decay of Correlation c = dd (d 1)(d+1) hardcore model: (Weak Spatial Mixing, WSM) uniqueness threshold: • λ ≤ λc 㱻 WSM holds on (d+1)-regular tree 㱻 Gibbs measure is unique • [Weitz ‘06]: λ < λc 㱺 FPTAS for graphs with max-degree ≤ d+1 • [Galanis, Štefankovič, Vigoda ‘12; Sly, Sun ‘12]: λ > λc 㱺 inapproximable unless NP=RP WSM: Pr[v∈I | σ] does not depend on σ when l→∞ I ∼μ
Decay of Correlation (Weak Spatial Mixing,WSM) Pr[e∈M|o]e monomerdimer model: L→0∞ M-u regular tree 99…999 boundary condition o:fixing leaf-edges at level l to be occupied/unoccupied by M WSM:Pr[e∈M|]does not depend on o when /∞ WSM always holds+Gibbs measure is always unique [Jerrum,Sinclair'89]:FPRAS for all graphs [Bayati,Gamarnik,Katz,Nair,Tetali'08]:FPTAS for graphs with bounded max-degree
regular tree ` ! 1 boundary condition σ : fixing leaf-edges at level l to be occupied/unoccupied by M Decay of Correlation (Weak Spatial Mixing, WSM) • WSM always holds 㱻 Gibbs measure is always unique • [Jerrum, Sinclair ’89]: FPRAS for all graphs • [Bayati, Gamarnik, Katz, Nair, Tetali ’08]: FPTAS for graphs with bounded max-degree WSM: Pr[e∈M | σ] does not depend on σ when l→∞ monomer-dimer model: Pr[e 2 M | ] e M ∼μ
CSP (Constraint Satisfaction Problem) 2 degree degree =2 max-degree≤d ≤d matching constraint matchings: variables xi∈{0,1} (at-most-1)
CSP (Constraint Satisfaction Problem) 1 2 3 4 5 6 a b c d e f g 1 2 3 4 5 6 a b c d e f g matchings: variables xi 2 {0, 1} matching constraint (at-most-1) degree ≤ d degree = 2 max-degree ≤ d