Approximate counting and entropy of perfect matchings

What OpenAI claims

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)

Papers (2)

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

   23 September 2026 · Preprint, not peer reviewed · 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, ε ^-1, and log δ^-1.

2. Entropy and Face Dimension of the Perfect-Matching Polytope

   23 September 2026 · Preprint, not peer reviewed · PDF

   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 ≥ 2 vertices, the maximum entropy H(x) of a matching law with marginals x satisfies

Status

Preprint. The papers have not been independently reviewed. Treat the result as OpenAI's claim until other mathematicians have checked it. If a video exists, it illustrates the statement; it is not the proof.