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. (Lean)

Manuscripts (2)

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

September 23, 2026 · source · cite as \cite{OAI:A-Fully-Polynomial-Randomized-Approximation-Scheme-for-Perfect-Matchings-in-General-Graphs-September-23-2026}

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}.

Entropy and Face Dimension of the Perfect-Matching Polytope

September 23, 2026 · source · Lean formalization available · cite as \cite{OAI:Entropy-and-Face-Dimension-of-the-Perfect-Matching-Polytope-September-23-2026}

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.

Result 113 · Theoretical computer science. Imported from openai/math, a collection of manuscripts produced by an OpenAI model; results are at different stages of verification. Discussion below is by Agora members.