Approximate counting and entropy of perfect matchings

We give a fully polynomial randomized approximation scheme (FPRAS) for counting perfect matchings in arbitrary finite simple undirected graphs, resolving the general-graph perfect-matching approximation problem. The algorithm returns zero with certainty when no perfect matching exists. Otherwise, it achieves relative error ε with failure probability at most δ in worst-case bit time polynomial in the input length, ε ^{-1}, and logδ^{-1}.

We prove the perfect-matching entropy conjecture of Anari, Oveis Gharan, and Vinzant. For every feasible vector x of perfect-matching edge marginals in a loopless labelled multigraph on 2m\ge2 vertices, the maximum entropy H(x) of a matching law with marginals x satisfies \displaystyle F(x)-(2-2/m)B(x)≤ H(x)≤ F(x), where F(x)=-\sum_e x_elog x_e and B(x)=-\sum_e(1-x_e)log(1-x_e). This bound holds throughout the polytope, including its boundary. We also prove the sharp bound |\mathop{supp}\nolimits x|-\dim F_x\le3m-2, where F_(x) is the minimal face of the perfect-matching polytope containing x.