A rooted entropy bound for perfect matchings

Abstract

Let H_G(x) be the maximum entropy of a perfect-matching law with prescribed edge marginals x in a finite loopless multigraph. We prove that, for every vertex v, H_G(x) is at least -sum_e x_e log x_e + (3/2) sum_{e not incident to v} (1-x_e) log(1-x_e). On 2m vertices this gives a coefficient (3/2)(1-1/m) in the unrooted complementary-entropy bound. The proof reserves the contribution of one vertex star. This makes the entropy deficit exactly additive under contraction of a tight odd cut and permits induction before a covariance second-variation argument. Boundary marginals and labelled parallel edges are included. We also obtain lower bounds for weighted partition functions and for graphs containing edge-disjoint perfect matchings.