文章基本信息

标题：Counting Hypergraph Matchings up to Uniqueness Threshold
本地全文：下载
作者：Renjie Song ; Yitong Yin ; Jinman Zhao 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：60
页码：46:1-46:29
DOI：10.4230/LIPIcs.APPROX-RANDOM.2016.46
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 monomer-dimer model (graph matchings). For this model, the critical activity lambda_c= (d^d)/(k (d-1)^{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 2lambda_c, there is no PRAS for the partition function or the log-partition 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 non-uniqueness of infinite Gibbs measure is not realizable by any finite gadgets.
关键词：approximate counting; phase transition; spatial mixing