A rooted entropy bound for perfect matchings
Abstract
Let be the maximum entropy of a perfect-matching law with prescribed edge marginals in a finite loopless multigraph. We prove that, for every vertex ,
On vertices this gives a coefficient 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.
Supplementary files
Comments
MathDB backfill of 10.5281/zenodo.23274113. Already released on Zenodo; retain existing DOI. Self-contained relative to OpenAI scope; exact hypotheses and conditional dependencies are in the unchanged paper.