Counting perfect matchings in general graphs: OpenAI FPRAS, simplified proof
Result confirmed
Importance: major (4 of 5)The takeaway
Approximately counting perfect matchings is easy for bipartite graphs (Jerrum–Sinclair–Vigoda, 2004) but had no polynomial-time scheme for general graphs. OpenAI’s 23 Sept release (family 113) claimed a fully polynomial randomized approximation scheme for all graphs, built on a restricted Poincaré inequality for pairs of matchings, and a Lean development. On 19 Oct Chenghua Liu and Boning Meng posted ‘a simplified, self-contained proof of OpenAI’s FPRAS’. It keeps the same parameter bounds and avoids the original auxiliary vertices and tree constructions. The same release also claimed the Anari–Oveis Gharan–Vinzant perfect-matching entropy conjecture.
Status
- Claim
Result confirmed
- Our reporting
- High confidence
- Verification
- Lean-verified
- Importance
- Major (4 of 5)
- Last verified
- 30 October 2026
Your AI and this story
- GPT-6 Astra172 days after its cutoff
- Claude Opus 5.5111 days after its cutoff
- Gemini 4 Argon202 days after its cutoff
- Grok 4.7141 days after its cutoff
None of these four assistants can know about it. The closest, Claude Opus 5.5, stops 111 days before it.
Key facts
- OpenAI family summary (openai/math): ‘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’
- Liu–Meng abstract (verbatim): ‘We give a simplified, self-contained proof of OpenAI’s FPRAS for counting perfect matchings in general graphs. As in the original proof, we use a restricted Poincaré inequality for two matchings to sample weighted perfect matchings and estimate their total weight. We simplify the proof of this inequality by isolating parts of alternating cycles directly on the original vertex set … This avoids the auxiliary vertices and tree constructions used in the original proof … and yields the same FPRAS guarantee.’
- How OpenAI’s proof works (Liu–Meng’s summary): thresholded connected components form a hierarchy; OpenAI ‘use these connection thresholds to assign auxiliary weights to vertex pairs’, giving completed weights within a polynomial factor of hierarchical reference weights, and compare two independent matchings through their alternating cycles
- Background: the permanent/bipartite case is Jerrum–Sinclair–Vigoda (2004); whether perfect matchings in general (non-bipartite) graphs admit an FPRAS was a long-standing open question in approximate counting
- Formal side: Lean scope lean/docs/113.md; the family’s Lean challenge was accepted in oai-math-revised’s community comparator run (26 Oct), per our family audit
- Verification status: OpenAI preprint (not refereed) with Lean development, plus an independent simplified proof on arXiv (not refereed); we found no expert commentary beyond the oai-math-revised notes
What happened
Counting perfect matchings exactly is #P-hard. For bipartite graphs, Jerrum, Sinclair and Vigoda found a randomized approximation scheme in 2004. For general graphs no such scheme was known. OpenAI’s September release claimed one, with a proof built on a Poincaré inequality for pairs of matchings and a Lean formalisation.
On 19 Oct Chenghua Liu and Boning Meng posted a shorter, self-contained proof of the same algorithm’s guarantee. They follow OpenAI’s strategy but handle the alternating cycles directly, without the auxiliary construction of the original.
Why it matters
A famous algorithmic question now has a machine-checked claim and an independent human proof. Few results in OpenAI’s release have this much support. The OpenAI preprint and the simplified proof are both still unrefereed.
Sources
4 sources from 2 sites. Numbers match the chips in the text.
4 sources: 4 primary
Primary
- arXiv 2610.26803: A simplified proof of the FPRAS for counting perfect matchings (Liu, Meng)arxiv.org, paper
- openai/math: A Fully Polynomial Randomized Approximation Scheme for Perfect Matchings in General Graphs (23 Sept 2026)github.com, paper
- openai/math: Entropy and Face Dimension of the Perfect Matching Polytopegithub.com, paper
- openai/math Lean scope for family 113github.com, code
Changes
- Filed from lead; Liu–Meng abstract and PDF read (science agent)