Counting Perfect Matchings: OpenAI Claims a Fast Approximation

About this video

A perfect matching pairs every vertex of a graph with exactly one neighbour, like the double bonds of a molecule. Counting them exactly is #P-hard, and fast approximate counting was known only for bipartite graphs, where Jerrum, Sinclair and Vigoda gave a randomized scheme in 2004. OpenAI claims a fully polynomial randomized approximation scheme for every finite simple graph, including graphs with odd cycles: it returns zero exactly when there is no perfect matching, and otherwise reaches any relative error you ask for in polynomial time. A companion preprint proves the perfect-matching entropy conjecture of Anari, Oveis Gharan and Vinzant. The animation is computed on the buckyball C60, which has 12 pentagons, so it is not bipartite: an exact search finds all 12,500 perfect matchings, a simple random-guess estimator averaged over 20,000 tries approaches that number, and the uniform law on matchings uses each hexagon-hexagon bond 44% of the time with an entropy of 13.61 bits. The estimator shown is a classic illustration, not OpenAI's algorithm. These are OpenAI's preprints, not yet peer reviewed; a Lean formalisation is listed.

Papers (OpenAI, catalogue result 113):
- A Fully Polynomial Randomized Approximation Scheme for Perfect Matchings in General Graphs: github.com/openai/math/blob/main/preprints/A-Fully-Polynomial…
- Entropy and Face Dimension of the Perfect-Matching Polytope: github.com/openai/math/blob/main/preprints/Entropy-and-Face-D…

The animation illustrates the result; it is not a proof.

Gradient Damage: mathematics you can see, equations you can hear.
youtube.com/@gradientdamage

Every result explained: gradientdamage.com/p/113