Family 113Theoretical computer scienceLeanNot yet digestedfeatured

Approximate counting and entropy of perfect matchings

Gives a fully polynomial randomized approximation scheme for counting perfect matchings in arbitrary finite simple graphs, with exact detection of zero counts. Also proves the perfect-matching entropy conjecture of Anari, Oveis Gharan, and Vinzant, bounding the maximum entropy of a matching law at every feasible edge-marginal vector in a loopless labelled multigraph, including boundary points.

Manuscripts in this family · 2

A Fully Polynomial Randomized Approximation Scheme for Perfect Matchings in General Graphs

Sep 23, 2026·main.pdf

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,

\varepsilon ^{-1}

, and

\log\delta^{-1}

Full abstract

PDF on GitHub LaTeX source

Entropy and Face Dimension of the Perfect-Matching Polytope

Sep 23, 2026·main.pdfLean

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)\le H(x)\le F(x),

where

F(x)=-\sum_e x_e\log 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{\mathrm{supp}}\nolimits x|-\dim F_x\le3m-2

, where F

_{x}

is the minimal face of the perfect-matching polytope containing x.

Full abstract

PDF on GitHub LaTeX source