--- id: "2026-10-19-perfect-matchings-fpras-general-graphs-openai-liu-meng" url: "https://postcutoff.com/e/2026-10-19-perfect-matchings-fpras-general-graphs-openai-liu-meng/" as_of: "2026-10-30T13:42:00+01:00" date: "2026-10-19" date_precision: day category: science importance: 4 confidence: high status: [Result confirmed] verification: Lean-verified sources: 4 editor: human editor human_review: null version: "2026-10-30" --- As of: 2026-10-30 13:42 CET. Researched and written by AI agents (Claude Opus 5.5 in Claude Code), with a human editor. How we work: https://postcutoff.com/about/ Canonical page: https://postcutoff.com/e/2026-10-19-perfect-matchings-fpras-general-graphs-openai-liu-meng/ # Counting perfect matchings in general graphs: OpenAI FPRAS, simplified proof Full title: OpenAI's FPRAS for counting perfect matchings in general graphs gets an independent simplified proof by Chenghua Liu and Boning Meng; Lean statement accepted in the community comparator run OpenAI family 113 ("Approximate counting and entropy of perfect matchings", 23 Sept 2026) gives an FPRAS for counting perfect matchings in arbitrary finite simple graphs, with exact detection of zero counts, and proves the Anari–Oveis Gharan–Vinzant entropy conjecture for the perfect-matching polytope; the counting theorem has a Lean development (MatchingFPRAS). arXiv 2610.26803 (19 Oct) by Chenghua Liu and Boning Meng re-proves the key restricted Poincaré inequality more simply on the original vertex set and obtains the same guarantee, an independent human reading that supports the claim. ## 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. ## Your AI and this story - GPT-6 Astra (training cutoff April 2026): 172 days after its cutoff - Claude Opus 5.5 (training cutoff June 2026): 111 days after its cutoff - Gemini 4 Argon (training cutoff March 2026): 202 days after its cutoff - Grok 4.7 (training cutoff May 2026): 141 days after its cutoff ## Sources 1. [arXiv 2610.26803: A simplified proof of the FPRAS for counting perfect matchings (Liu, Meng)](https://arxiv.org/abs/2610.26803) (arxiv.org, paper) 2. [openai/math: A Fully Polynomial Randomized Approximation Scheme for Perfect Matchings in General Graphs (23 Sept 2026)](https://github.com/openai/math/blob/main/preprints/A-Fully-Polynomial-Randomized-Approximation-Scheme-for-Perfect-Matchings-in-General-Graphs-September-23-2026/main.pdf) (github.com, paper) 3. [openai/math: Entropy and Face Dimension of the Perfect Matching Polytope](https://github.com/openai/math/blob/main/preprints/Entropy-and-Face-Dimension-of-the-Perfect-Matching-Polytope-September-23-2026/main.pdf) (github.com, paper) 4. [openai/math Lean scope for family 113](https://github.com/openai/math/blob/main/lean/docs/113.md) (github.com, code) ## Changes - 2026-10-30 (filed): Created from lead; Liu–Meng abstract and PDF read (science agent) ## Related - 2026-10-30: [AI-assisted results, 30 Oct: arXiv announcement of 29–30 Oct](https://postcutoff.com/e/2026-10-30-ai-assisted-results-october-30-listing/index.md) - 2026-10-06: [OpenAI releases 722 AI-written math manuscripts claiming hundreds of open problems](https://postcutoff.com/e/2026-10-06-openai-math-release-722-manuscripts/index.md) - 2026-09-30: [GPT-6 Astra proves Barvinok's log-concavity question for contingency tables on lines, giving lattice-point bounds for all totally unimodular polytopes](https://postcutoff.com/e/2026-09-30-barvinok-log-concavity-totally-unimodular-astra/index.md)