Speaker: Yitong Yin

Title: Phase transition of hypergraph matchings

Abstract:

Abstract: We study the problem of approximately counting weighted matchings in hypergraphs of bounded maximum edge size and maximum degree. The problem is expressed as evaluating the partition function, which is the weighted sum of all macthings in a hypergraph where each macthing M is assigned a weight λ|M| in terms of a fixed activity parameter λ. This model unifies two important problems in approximate counting arising from statistical physics: counting independent set (the hardcore model) and counting matchings (the monomer-dimer model).

We show that for hypergraph matchings, the critical activity λc= dd/k(d-1)(d+1) is the uniqueness threshold for the Gibbs measure on (d+1)-uniform (k+1)-regular hyper-tree, and when λ<λc, the hypergraphs of maximum edge size at most d+1 and maximum degree at most k+1 exhibit strong spatial mixing. As a consequence, there is an FPTAS for counting matchings in hypergraphs of bounded maximum edge size at most and bounded maximum degree as long as the uniqueness condition is satisfied.

As for the inapproximability, it can be easily shown that there is no FPRAS for the problem when λ>2λc, unless NP=RP. This left an intriguing gap between λc and 2λc. A key step towards tight inapproximability result is the local weak convergence from a sequence of finite graphs to the extremal measures for the uniqueness threshold on the infinite tree. For hypergraph matchings, we discover that such local weak convergence does not exist for any sequence of finite hypergraphs, which indicates that approximate counting on hypergraphs (or general CSPs) contains much richer structure yet to be understood.