《计算机科学》相关教学资源（参考文献）Phase transition of hypergraph matchings

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]:λ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 㱺 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

CSP (Constraint Satisfaction Problem) degree degree =2 max-degree≤d ≤d 8 matching constraint matchings: variables xi∈{0,1} (at-most-1) matching constraint independent sets: variables i∈{0，l} (at-most-1) partition function: Z= 入川1 i∈{0，l}n satisfying all constraints

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: independent sets: variables xi 2 {0, 1} matching constraint (at-most-1) matching constraint (at-most-1) variables xi 2 {0, 1} max-degree ≤ d partition function: Z = X ~x2{0,1}n satisfying all constraints ￾k~xk1 degree ≤ d degree = 2

CSP (Constraint Satisfaction Problem) deg≤d+l deg≤k+l c2 t> c☒ 4 c函 a Boolean at-most-1 variables constraints partition function: ∑ 入川1 i∈{0,1}n satisfying all constraints

CSP (Constraint Satisfaction Problem) Boolean variables deg ≤ d+1 deg ≤ k+1 x1 x2 x3 x4 x5 c1 c2 c3 c4 c5 c6 c7 Z = X ~x2{0,1}n satisfying all constraints ￾k~ xk1 partition function: at-most-1 constraints

Hypergraph matching hypergraph =(V,E) vertex set V hyperedge e∈E,eCV a matching is an subset MCE of disjoint hyperedges partition .U] Zλ(H)= ∑ λM川 .U4 i. functions: M:matching of H ,5 .29 8 es .6 e2 es Gibbs λXM distribution: u(M)= Z(孔)

v3 e1 v1 v2 v4 v8 v7 e2 e3 e5 v9 v6 v5 e4 v1 v2 v3 v4 v5 v6 v7 v8 v9 e1 e2 e3 e4 e5 Hypergraph matching Z￾(H) = X M: matching of H ￾|M| hypergraph H = (V,E) vertex set V hyperedge e 2 E, e ⇢ V a matching is an subset M⊂E of disjoint hyperedges µ(M) = ￾|M| Z￾(H) partition functions: Gibbs distribution:

matchings in hypergraphs of max-degree sk+1 and max-edge-sizes d+1 matching 01 .4 th2. incidence graph primal: .5 ,28 e3 6 9 e2 e3 5 6 dual: CSP defined by matching(packing)constraint 7 06 independent set independent sets in hypergraphs of max-degree sd+1 and max-edge-size sk+1 independent sets:a subset of non-adjacent vertices (to be distinguished with:vertex subsets containing no hyperedge as subset)

v3 e1 v1 v2 v4 v8 v7 e2 e3 e5 v9 v6 v5 e4 v1 v2 v3 v4 v5 v6 v7 v8 v9 e1 e2 e3 e4 e5 matchings in hypergraphs of max-degree ≤ k+1 and max-edge-size ≤ d+1 v3 e1 v1 v2 v4 v8 v7 e2 e3 e5 v9 v6 v5 e4 * * * * * * * * * * * * * * v5 * v6 * e2 * v1 * v2 * e1 * v3 * v4 * e5 * e3 * e4 * v7 * v8 * v9 * incidence graph primal: dual: v3 e1 v1 v2 v4 v8 v7 e2 e3 e5 v9 v6 v5 e4 * * * * * * * * * * * * * * v5 * v6 * e2 * v1 * v2 * e1 * v3 * v4 * e5 * e3 * e4 * v7 * v8 * v9 * matching independent set CSP defined by matching(packing) constraint independent sets in hypergraphs of max-degree ≤ d+1 and max-edge-size ≤ k+1 independent sets: a subset of non-adjacent vertices (to be distinguished with: vertex subsets containing no hyperedge as subset)

Known results deg≤d+l ☑deg≤k+l C2 independent sets of hypergraphs of max-degree≤d+1 and max-edge-size≤k+l C4 cs partition function: Z= 入川1 元∈{0,1}n satisfying Boolean at-most-1 all constraints variables constraints Classification of approximability in terms of )d,k? ●k=l:hardcore model d=1:monomer-dimer model ●forλ=1： [Dudek,Karpinski,Rucinski,Szymanska 2014]:FPTAS when d=2,k<2 [Liu and Lu 2015]FPTAS when d=2,k<3

Known results • k=1: hardcore model • d=1: monomer-dimer model •for λ=1: •[Dudek, Karpinski, Rucinski, Szymanska 2014]: FPTAS when d=2, k≤2 •[Liu and Lu 2015] FPTAS when d=2, k≤3 Boolean variables deg ≤ d+1 deg ≤ k+1 x1 x2 x3 x4 x5 c1 c2 c3 c4 c5 c6 c7 at-most-1 constraints Z = X ~x2{0,1}n satisfying all constraints ￾k~ xk1 partition function: independent sets of hypergraphs of max-degree ≤ d+1 and max-edge-size ≤ k+1 Classification of approximability in terms of λ, d, k ?