Browse › Theoretical computer science › 113 Approximate counting and entropy of perfect matchings
A Fully Polynomial Randomized Approximation Scheme for Perfect Matchings in General Graphs
Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion
Edit NOTES.md · Existing issues · Source on GitHub
Abstract
We give a fully polynomial randomized approximation scheme (FPRAS) for counting perfect matchings in arbitrary finite simple undirected graphs, resolving the general-graph perfect-matching approximation problem. The algorithm returns zero with certainty when no perfect matching exists. Otherwise, it achieves relative error ε with failure probability at most δ in worst-case bit time polynomial in the input length, $\varepsilon ^{-1}$, and $\log\delta^{-1}$.
If the PDF does not display here, open it directly: Open PDF.
Notes
No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.
Automatically collected notes (unreviewed)
work in progress
Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.
Follow-up works
- Chenghua Liu, Boning Meng, A simplified proof of the FPRAS for counting perfect matchings (arXiv:2610.26803, 19 Oct 2026). Gives a simplified proof of this paper's FPRAS by establishing the comparison argument of its Sections 4–6 on the original vertex set without auxiliary vertices and tree constructions, while citing and reusing its encoding, replication and mixing/finite-precision results (Lemma 6.4, Lemma 7.2, Theorem 7.3, Section 9).
Comments and discussion
- microprediction, comment in Add OpenAI results page with applied and difficulty scores (microprediction/pure PR #20) (GitHub, 7 Oct 2026). A correction to a third-party catalogue note on item 113 that separates the earlier Jerrum–Sinclair FPRAS for the monomer–dimer partition function from the newly claimed FPRAS for perfect matchings in general graphs.
Formalization
- OpenAI, Approximate counting and entropy of perfect matchings: Lean scope note (OpenAI math release, 2026-10-06). Describes the formalized FPRAS statement for every finite simple graph (a fixed randomized machine with worst-case polynomial bit time and exact zero detection), with comparator statement
MatchingFPRAS.lean. [family-level]
Related prior literature mentioned by others
- Martin Dyer and Haiko Müller, Counting Perfect Matchings and the Switch Chain (SIAM Journal on Discrete Mathematics 33(3), 1146–1174, 2019). Cited by Liu and Meng's follow-up for rapid mixing of the switch chain on quasimonotone graphs and slow-mixing examples in a larger hereditary class, explaining the limitations of two-edge switches for the general problem.
Possibly relevant literature (found by the agent, not checked)
- Farzam Ebrahimnejad, Ansh Nagda, Shayan Oveis Gharan, Counting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs (arXiv:2103.08683, ITCS 2022). Polynomial-time sampling and counting via the Jerrum–Sinclair chain for regular strong-expander non-bipartite graphs, relevant to the introduction's survey of non-bipartite special cases.
- Alexander Barvinok, Approximating permanents and hafnians (arXiv:1601.07518, Discrete Analysis 2017). Quasi-polynomial approximation of log-hafnians for matrices with entries in [δ,1], relevant to the paper's comparison with density-restricted earlier results.
- Yeganeh Alimohammadi, Nima Anari, Kirankumar Shiragur, Thuy-Duong Vuong, Fractionally Log-Concave and Sector-Stable Polynomials: Counting Planar Matchings and More (arXiv:2102.02708, 2021). FPRAS for counting matchings of a given size in planar, not necessarily bipartite graphs, relevant to the paper's corollary on fixed-cardinality matchings.
Elsewhere
- VibeMathed: Problem record
- Emergent Mind: family 113
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:A-Fully-Polynomial-Randomized-Approximation-Scheme-for-Perfect-Matchings-in-General-Graphs-September-23-2026,
author = {{OpenAI}},
title = {{A Fully Polynomial Randomized Approximation Scheme for Perfect Matchings in General Graphs}},
howpublished = {OpenAI Math Release preprint
\href{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}{OAI:A-Fully-Polynomial-Randomized-Approximation-Scheme-for-Perfect-Matchings-in-General-Graphs-September-23-2026}},
year = {2026}
}Lean formalization
OpenAI provides Lean files for this family: lean/docs/113.md. The Lean statements have not been checked by people against the paper's claims.
Family 113: Approximate counting and entropy of perfect matchings
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, bounding the maximum entropy of a matching law at every feasible edge-marginal vector in a loopless labelled multigraph, including boundary points.
Other papers in this family:
- Entropy and Face Dimension of the Perfect-Matching Polytope · September 23, 2026