Abstract
We study the problem of approximately counting matchings in hypergraphs of bounded maximum degree and maximum size of hyperedges. With an activity parameter lambda, each matching M is assigned a weight lambda^{M}. The counting problem is formulated as computing a partition function that gives the sum of the weights of all matchings in a hypergraph. This problem unifies two extensively studied statistical physics models in approximate counting: the hardcore model (graph independent sets) and the monomerdimer model (graph matchings).
For this model, the critical activity lambda_c= (d^d)/(k (d1)^{d+1}) is the threshold for the uniqueness of Gibbs measures on the infinite (d+1)uniform (k+1)regular hypertree. Consider hypergraphs of maximum degree at most k+1 and maximum size of hyperedges at most d+1. We show that when lambda < lambda_c, there is an FPTAS for computing the partition function; and when lambda = lambda_c, there is a PTAS for computing the logpartition function. These algorithms are based on the decay of correlation (strong spatial mixing) property of Gibbs distributions. When lambda > 2lambda_c, there is no PRAS for the partition function or the logpartition function unless NP=RP.
Towards obtaining a sharp transition of computational complexity of approximate counting, we study the local convergence from a sequence of finite hypergraphs to the infinite lattice with specified symmetry. We show a surprising connection between the local convergence and the reversibility of a natural random walk. This leads us to a barrier for the hardness result: The nonuniqueness of infinite Gibbs measure is not realizable by any finite gadgets.
BibTeX  Entry
@InProceedings{song_et_al:LIPIcs:2016:6669,
author = {Renjie Song and Yitong Yin and Jinman Zhao},
title = {{Counting Hypergraph Matchings up to Uniqueness Threshold}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
pages = {46:146:29},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770187},
ISSN = {18688969},
year = {2016},
volume = {60},
editor = {Klaus Jansen and Claire Mathieu and Jos{\'e} D. P. Rolim and Chris Umans},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6669},
URN = {urn:nbn:de:0030drops66690},
doi = {10.4230/LIPIcs.APPROXRANDOM.2016.46},
annote = {Keywords: approximate counting; phase transition; spatial mixing}
}
Keywords: 

approximate counting; phase transition; spatial mixing 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016) 
Issue Date: 

2016 
Date of publication: 

06.09.2016 