Approximate counting and entropy of perfect matchings
From OpenAI Aftermath
Approximate counting and entropy of perfect matchings concerns two problems about perfect matchings in graphs that need not be bipartite: whether the number of perfect matchings of an arbitrary graph can be approximated by a fully polynomial randomized approximation scheme (FPRAS), a question raised by Jerrum and Sinclair, and the perfect-matching entropy conjecture of Anari, Oveis Gharan and Vinzant. Two manuscripts dated 23 September 2026 in OpenAI's public mathematics collection (github.com/openai/math) claim an FPRAS for counting perfect matchings in every finite simple graph and pointwise entropy bounds on the perfect-matching polytope that prove the entropy conjecture. The collection includes Lean formalizations of the counting scheme and of the entropy bounds. This page summarizes the published claims and lists publicly available follow-up work. Statements are the respective authors' claims; the publication of a paper, code or a formal proof is not presented here as independent verification.
Background
- As recounted in the introductions of the manuscripts:
- Edmonds gave a polynomial-time algorithm for finding a maximum matching, Valiant proved that exact counting of perfect matchings is #P-complete already for bipartite graphs, and Kasteleyn's Pfaffian method counts perfect matchings of planar graphs exactly. Jerrum and Sinclair gave an FPRAS for the total number of matchings and for perfect matchings when the ratio of near-perfect to perfect matchings is polynomially bounded, and raised the general-graph question; Jerrum, Sinclair and Vigoda gave an FPRAS for the permanent of every nonnegative matrix, the bipartite case. Štefankovič, Vigoda and Wilmes showed that chains of the Jerrum–Sinclair–Vigoda type fail on some nonbipartite graphs; later bipartite improvements are due to Bezáková, Štefankovič, Vazirani and Vigoda, to Chen, Vigoda and Yang, and to Chen, Guo, Vigoda and Yang, and Yi treated hafnians under a minimum-degree condition.
- For the entropy question, Shearer's inequality gives the upper bound, Edmonds' theorem describes the perfect-matching polytope by degree, nonnegativity and odd-cut constraints, and the inequalities of Schrijver and of Gurvits give the bipartite comparison. Anari, Oveis Gharan and Vinzant asked whether the maximum binary entropy of a perfect-matching mean exceeds the logarithm of the number of perfect matchings by at most a linear function of the number of vertices. Exponential lower counts for structured graph classes are due to Esperet, Kardoš, King, Král' and Norine, to Abdi, Cornuéjols, Dadush and Dalirrooyfard, and to Ebrahimnejad, Nagda and Oveis Gharan.
The original results
- Claim (counting). Theorem 1.1 of A fully polynomial randomized approximation scheme for perfect matchings in general graphs states that there is a randomized algorithm which, given a finite simple undirected graph G and rational 0 < ε < 1 and 0 < δ < 1/2, returns a nonnegative rational estimate within relative error ε of the number of perfect matchings with probability at least 1 − δ, returns zero with certainty when there is no perfect matching, and runs in worst-case bit time polynomial in the input length, ε−1 and log δ−1. Its final section derives counting schemes for subgraphs with prescribed degrees and for matchings of a given size.
- Claim (entropy). Theorem 1.1 of Entropy and face dimension of the perfect-matching polytope states that for a loopless multigraph on 2m ≥ 2 vertices and every point x of its perfect-matching polytope, the maximum entropy H(x) of a matching law with edge marginals x satisfies F(x) − (2 − 2/m)B(x) ≤ H(x) ≤ F(x), where F and B are the sums of −xe log xe and of −(1 − xe) log(1 − xe). The manuscript states that this answers the Anari–Oveis Gharan–Vinzant question with the bound log N(G) ≤ max(F + B) ≤ log N(G) + 3m − 2, and it proves the sharp face-dimension bound that the support size of x minus the dimension of its minimal face is at most 3m − 2, together with lower counts for graphs with k edge-disjoint perfect matchings.
- Method, as described: the counting algorithm starts from the complete graph and gradually suppresses the nonedges of G, estimating ratios of successive partition functions; vertex scales keep the ratios of two-hole partition functions balanced, and marked probe edges in an enlarged graph expose them. The sampler works on a product of perfect-matching spaces of an enlarged coloured graph with exchanges of alternating cycles between coordinates, and its spectral gap comes from an energy inequality for pairs of coordinates, proved through a quadrangulation and a signed cell identity and then extended to arbitrary functions by an ordered product decomposition. The entropy bound combines the face-dimension estimate with a covariance calculation for the maximum-entropy law restricted to the minimal face.
- Sources. The manuscripts A fully polynomial randomized approximation scheme for perfect matchings in general graphs and Entropy and face dimension of the perfect-matching polytope at commit
1581d4c. - Formalization, as described by the repository. The scope note states that the formalization gives a fully polynomial randomized approximation scheme for counting perfect matchings in every finite simple undirected graph, as a fixed finite-alphabet randomized machine whose worst-case running time is polynomial in the binary input length, ε−1 and log(δ−1), including on unsuccessful random tapes, and that it proves the entropy bounds for m ≥ 1, including boundary points of the polytope. It also states that a further statement concerns the face obtained by expanding a degree-three vertex into a triangle, and that the paper's sharp global face-dimension bound is not part of that selected statement. The Comparator statements are
MatchingFPRAS.lean,MatchingEntropy.lean,BinaryMatching.lean,SingletonLoopMatching.lean,MatchingEntropyBounds.leanandTriangleFace.lean.
Public follow-up work
| Date | Work | Relation | Public claim | Public status (checked 20 October 2026) |
|---|---|---|---|---|
| 2026-10-07 (manuscript date) | R. Gounder, Mathematical Frontiers in the OpenAI Research Release (GitHub) | Comparative review | Includes a case study of the counting manuscript. It summarizes the hole-capacity bound (Theorem 3.1), the weighted subdivision and coloured tree-bag enlargement, and the sampler with exchanges between two matching coordinates; it notes that the pair-energy theorem (Theorem 6.1) bounds only additive pair functions and that Lemma 7.2 upgrades it by an ordered product decomposition with replicated weight tiers, the replication count being 32L for a large polynomial L. It observes that the scope note lists the counting scheme but only selected entropy and face statements, so that the algorithmic theorem and each geometric companion should keep their separate evidence status. | A 25-page review. The README states that its checks "do not independently establish the underlying release theorems". |
| 2026-10-07 | R. Gounder, Kohze/counting-and-sampling-review, Approximate Counting and Uniform Sampling: A Critical Review of Matroid Intersections, Contingency Tables, and Graph Switch Chains | Review (narrative) | A narrative review of six counting and sampling manuscripts of the collection, including the perfect-matching manuscript, relating their stated guarantees to the earlier literature through reductions, worked probability laws and accuracy and runtime models. | GitHub repository with a manuscript; its LaTeX source includes a dedicated AI disclosure. |
| 2026-10-08 | MathVet (GitHub; review of openai/math, tables at repository commit c76f1e4, 14 October 2026) |
Review (fidelity of the formal statements) | Rates this family "full" for its six Comparator challenges, with no review note for the counting scheme and the pointwise entropy bounds, and notes that the sharp face-dimension bound is not stated, the face statement being only the correspondence under triangle expansion. Among the definitions to check it lists the hand-written randomized machine, with one fair coin per step and a sparse binary input encoding. It records a sandboxed Comparator pass for each of the six challenges. | MathVet states that it does not claim any theorem false and reports what was machine-checked as stated. |
| 2026-10-10 | cert-machine, openai/math lane K: MatchingFPRAS, MatchingEntropy, BinaryMatching, SingletonLoopMatching, MatchingEntropyBounds and TriangleFace | Verification (two kernels) | Records that Lean's default kernel and the nanoda kernel accept the solutions of all six challenges, in 1,207 s for MatchingFPRAS and between 138 s and 670 s for the others. The project reports two-kernel certification of 398 of 416 challenges of the collection. |
Repository. |
| 2026-10-10 to 2026-10-14 | con-leche development journal (tasks #348 and #353) | Verification (second kernel) | In its run over all Comparator challenges of the collection at commit fd4aeeb (task #348), con-leche and Lean's official kernel accepted five of the six challenges; for MatchingFPRAS the official kernel accepted while con-leche stopped with exit code 3 because its reduction fuel was exhausted on a deep recursion. After the changes of task #353, the journal records that con-leche accepts MatchingFPRAS (4.1 GB). |
Development journal. |
| 2026-10-16 | J. Jardine, Lattice24, referee review of the counting manuscript in JJardine919/openai-math-audit (archived at Zenodo 10.5281/zenodo.23422995) | Review (AI-assisted audit) | Reports no gap. The reviewer states that it read and checked Sections 1 to 8 and skimmed the section on prescribed degrees, and that it re-derived the pair-energy inequality and the replica spectral-gap argument line by line; given the significance of the claim, it recommends independent expert review of these steps, and it notes that the constants are polynomial but astronomically large. | Part of an audit of the collection's manuscripts that the audit describes as complete. The review is published under CC BY 4.0. |
| 2026-10-19 | C. Liu, B. Meng, A simplified proof of the FPRAS for counting perfect matchings, arXiv:2610.26803v1 | Simplification | Gives a simplified, self-contained proof of OpenAI's FPRAS for counting perfect matchings. As in the original proof it uses a restricted Poincaré inequality for two matchings to sample weighted perfect matchings and estimate their total weight, and it simplifies the proof of this inequality by isolating parts of alternating cycles directly on the original vertex set, avoiding the auxiliary vertices and tree constructions; the abstract states that the parameter bounds and the FPRAS guarantee are preserved. | arXiv preprint, version 1 of 19 October 2026. |
Notes
- The earlier results are due to the authors named in the Background section, as recounted by the manuscripts.
- The list covers follow-ups found in public sources up to the date above; it is not a priority or completeness claim.
