A rooted entropy bound for perfect matchings

Myeongjin Kang

Abstract

Let HG(x)H_G(x) be the maximum entropy of a perfect-matching law with prescribed edge marginals xx in a finite loopless multigraph. We prove that, for every vertex vv,

HG(x)≥−∑exelog⁡xe+32∑e∉δ(v)(1−xe)log⁡(1−xe).H_G(x)\ge-\sum_e x_e\log x_e +\frac32\sum_{e\notin\delta(v)}(1-x_e)\log(1-x_e).

On 2m2m vertices this gives a coefficient 32(1−1/m)\frac32(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.

1

Supplementary files

  • proof-sources.json11.0 KBOpen
  • extract_sources.py601 BOpen

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.

Version history

Discussion 0