VibeMathedMath problems solved with AI
Sign in

A fully polynomial randomized approximation scheme for counting perfect matchings in general graphs

Counting perfect matchings exactly is #P-complete even for bipartite graphs (Valiant 1979). Jerrum and Sinclair (1989) gave an FPRAS for all matchings and for perfect matchings only when the ratio of near-perfect to perfect matchings is polynomially bounded; Jerrum, Sinclair and Vigoda (2004) removed that restriction in the bipartite case (the permanent of a nonnegative matrix). Stefankovic, Vigoda and Wilmes showed that chains of the Jerrum-Sinclair-Vigoda type cannot work on some nonbipartite graphs. Is there a fully polynomial randomized approximation scheme for the number Z(G)Z(G) of perfect matchings of an arbitrary graph GG, that is, a randomized algorithm returning Z^\widehat Z with (1−ε)Z(G)≤Z^≤(1+ε)Z(G)(1-\varepsilon)Z(G)\le \widehat Z\le(1+\varepsilon)Z(G) with probability at least 1−δ1-\delta, in time polynomial in the input size, ε−1\varepsilon^{-1} and log⁡δ−1\log\delta^{-1}?

Result
Proved(see note)
Status
Candidate (review pending)
AI contribution
AI-discovered
Method
Construction
Field
Approximate counting; Markov chain Monte Carlo
Posed by
Mark Jerrum and Alistair Sinclair, Approximating the permanent, SIAM J. Comput. 18 (1989), Section 7(i)
Year posed
1989
Years open
37y
Solved
2026-09-23
Model
Unreleased internal OpenAI model
Vendor
OpenAI
Collaborators
—
Verification
Lean-checked, statement unaudited
Publication
Announced
Collection
OpenAI math release (October 2026), version adc7f12
Significance
55 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

Theorem 1.1: a uniform classical randomized algorithm that, for any finite simple undirected graph GG and rationals 0<ε<10<\varepsilon<1, 0<δ<1/20<\delta<1/2, returns Z^≥0\widehat Z\ge0 with Pr⁡[(1−ε)Z(G)≤Z^≤(1+ε)Z(G)]≥1−δ\Pr[(1-\varepsilon)Z(G)\le\widehat Z\le(1+\varepsilon)Z(G)]\ge1-\delta, returns 0 with certainty when Z(G)=0Z(G)=0, and runs in worst-case bit time polynomial in the input length, ε−1\varepsilon^{-1} and log⁡δ−1\log\delta^{-1}. Corollaries give counting schemes for edge sets with prescribed degrees and for matchings of a given size. It is for unweighted simple graphs: it does not claim an FPRAS for hafnians with arbitrary nonnegative weights, and the polynomial's degree is not optimised.

What the AI did

The release README says the results were produced by an unreleased internal OpenAI model with a fixed procedure, on average about three hours of ChatGPT Pro thinking compute per result, and that some outputs build on earlier model results. This result is not among the README's exceptions (the Hodge conjecture for CM abelian varieties and the Re(s) > 11/12 zero-free region). The manuscript is authored 'OpenAI' and names no human author. The algorithm and its analysis are the model's; the paper says it uses a different state space from the Jerrum-Sinclair-Vigoda chain (products of perfect-matching spaces on an enlarged colored graph) to get around the Stefankovic-Vigoda-Wilmes obstruction. The README also cautions that unformalized results could have issues.

Verification

No independent mathematician has checked this yet. Checked here: Theorem 1.1 of the manuscript was read against the question as Jerrum and Sinclair raised it (Section 7(i) of their 1989 paper, as the manuscript cites it). The proof was not refereed. Lean: the release's Comparator challenge MatchingFPRAS (theorem OAI.MatchingFPRAS.thm_main, solution module OAI.Combinatorics.MatchingCount.Main, both present at the pinned commit) is not in the release's formalization catalogue (lean/formalization.yaml); it is reached through lean/docs/113.md. Its statement was read here: a single finite randomized Post-Turing machine, on an explicit binary encoding of any finite simple graph and rationals 0<ε<10<\varepsilon<1, 0<δ<1/20<\delta<1/2, halts on every random tape within C(input length+⌈ε−1⌉+⌈log⁡2δ−1⌉+1)dC(\text{input length}+\lceil\varepsilon^{-1}\rceil+\lceil\log_2\delta^{-1}\rceil+1)^d steps with a nonnegative rational, outputs 0 on every tape when there is no perfect matching, and is within relative error ε\varepsilon on at least a 1−δ1-\delta fraction of tapes. That is the headline claim. The development was not rebuilt here and the statement has not been independently audited.

Sources

Changelog1 change

Discussion