Counting any graph?

The claims, in plain words

A perfect matching pairs up all the vertices of a graph along its edges. Finding one is easy: Edmonds gave a polynomial-time algorithm in 1965. Counting them is another matter: Valiant showed in 1979 that exact counting is #P-complete, even for bipartite graphs, where the count is the permanent of a 0–1 matrix. For planar graphs, Pfaffian methods give exact counts.

The realistic goal is approximation: a fully polynomial randomized approximation scheme (FPRAS) gets within any relative error ε with probability at least 1 − δ, in time polynomial in the graph’s size, 1/ε and log(1/δ). Jerrum and Sinclair (1989) gave one for all matchings together, and for perfect matchings when near-perfect matchings, with two unmatched vertices, outnumber them at most polynomially. Jerrum, Sinclair and Vigoda removed that condition for bipartite graphs, approximating every nonnegative permanent. For general graphs the question stayed open, and Štefankovič, Vigoda and Wilmes showed that chains of the bipartite type fail on some graphs, whatever hole weights they use.

Result 113 is two OpenAI preprints, 45 pages each, dated September 23, 2026. The first claims an FPRAS for perfect matchings in every finite simple graph, in worst-case time polynomial in the input length, 1/ε and log(1/δ), returning zero with certainty when there is no perfect matching; the method also counts subgraphs with prescribed degrees and matchings of a given size. The second proves a pointwise entropy bound that settles a conjecture of Anari, Oveis Gharan and Vinzant: if x gives the probability of each edge in a random perfect matching of a graph on 2m vertices, the largest possible entropy H(x) of such a random matching satisfies F(x) − (2 − 2/m)·B(x) ≤ H(x) ≤ F(x), where F(x) = −Σ x_e log x_e and B(x) = −Σ (1 − x_e) log(1 − x_e).

What it doesn’t claim

The counting result is approximate and randomized: exact counting remains #P-complete. The entropy bound is pointwise and does not by itself give an algorithm; its optimized form gives log N ≤ max(F + B) ≤ log N + 3m − 2, the linear-error estimate Anari, Oveis Gharan and Vinzant asked for.

Where it stands

Posted as preprints

OpenAI, 45 pages each, dated September 23, 2026

Peer reviewed

Not yet

Checked in Lean

OpenAI published Lean proofs of the counting algorithm and the entropy bound; we have not run the checks

Last checked October 19, 2026. The preprints have not been revised. OpenAI published a Lean formalization of the counting algorithm as a fixed randomized machine with a worst-case polynomial running time, 415 files and 66,246 lines in the import closure, matched against its comparator statement, and of the entropy bound, 26 files and 5,172 lines, matched against its comparator; the sharp face-dimension bound is proved there as an internal lemma. Nothing outside Mathlib, with no unproved steps that we could find. We have not run the checks. Neither paper is among those OSVerify reviewed, and we have seen no expert review.

How the proof goes

1. From the complete graph. The algorithm starts from the complete graph, whose perfect matchings are easy to count, and gradually lowers the weights of the non-edges of G. Up to a tiny bias, the count for G is the starting count times a product of ratios of successive partition functions, each estimated by sampling. Vertex scales keep the ratios with two vertices deleted balanced.
2. An enlarged graph. Each edge becomes a weighted path, and weak clique edges are added in overlapping bags along a tree. A capacity bound built from bottleneck paths shows that, under balance, the extra edges at most double the partition function, so a sample uses only real edges at least half the time; a marked edge exposes the two-hole ratios for the next step.
3. A sampler on pairs of matchings. The chain runs on a product of perfect-matching spaces, with local switches and exchanges of alternating cycles between two coordinates, avoiding the near-perfect states where the bipartite approach breaks down. A quadrangulation adapted to the bag labels gives an exact signed identity for a whole cycle, bounding the variance of sums of one-coordinate functions by their energy; replicating coordinates across a ladder of nearby weights gives a spectral gap for all functions. The bottom tier, at unit weights, is counted and sampled exactly by dynamic programming on the tree.
4. The entropy bound. Shearer’s inequality gives H ≤ F. The lower bound uses Edmonds’ description of the perfect-matching polytope by odd cuts and the sharp estimate |supp x| − dim F_x ≤ 3m − 2, followed by a covariance calculation. A consequence: a graph on 2m vertices with k ≥ 2 edge-disjoint perfect matchings has at least k^m(1 − 1/k)^{2(m−1)(k−1)} ≥ k^m/e^2m−2 perfect matchings.

The numbers in the video

• Exact counts: the Petersen graph has 6 perfect matchings, the three-dimensional cube 9, the four-dimensional cube 272, the complete graph on 10 vertices 945; on a random bipartite graph the count equals the permanent.
• Fifteen ratios, each estimated from 4,000 samples while the weight of the Petersen graph’s non-edges inside the complete graph on 10 vertices was halved step by step, took 945 down to an estimate of 5.9 for the exact 6.
• At the uniform point of the complete graph on 10 vertices (each edge with probability 1/9), the entropy bounds read 3.45 ≤ log 945 = 6.85 ≤ 10.99.
• The counting corollary held for complete graphs up to 16 vertices (2,027,025 ≥ 3,435 for 16), and trivially for small cubes.

Read the source

• A Fully Polynomial Randomized Approximation Scheme for Perfect Matchings in General Graphs (PDF), 45 pages.
• Entropy and Face Dimension of the Perfect-Matching Polytope (PDF), 45 pages.
• The Lean scope note.
• The collection’s catalog, where this is result 113.

The 2 papers in this result

OpenAI groups related papers, such as alternative proofs, supporting results and consequences, into one result; we label the first paper it lists the main paper and the others companions.

• A Fully Polynomial Randomized Approximation Scheme for Perfect Matchings in General Graphs main paper
• Entropy and Face Dimension of the Perfect-Matching Polytope companion

Transcript

Spot a mistake?

This episode simplifies on purpose, but it shouldn’t be wrong. If something is, open an issue on GitHub or leave a comment on YouTube. Corrections are noted here with a date.