PreprintarXiv licencearXiv
A simplified proof of the FPRAS for counting perfect matchings
Abstract
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 and controlling the resulting error terms. This avoids the auxiliary vertices and tree constructions used in the original proof. The argument preserves the required parameter bounds and yields the same FPRAS guarantee.
Related
- An FPRAS for Counting Common Bases of Two Matroids
- Spanning Even Linear Forests with Isolated Edges Share the Anti-Ramsey Numbers of Perfect Matchings
- Perfect matchings in hypergraphs and Feige's inequality
- Covering Bridgeless Claw-Free Cubic Graphs with Perfect Matchings
- The Cycle Rank Threshold: Perfect Matchings and Bipartite Parter Graphs
BibTeX
@misc{liu2026simplified,
title = {{A simplified proof of the FPRAS for counting perfect matchings}},
author = {Chenghua Liu and Boning Meng},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.26803},
eprint = {2610.26803},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.26803},
}
RIS
TY - UNPB
TI - A simplified proof of the FPRAS for counting perfect matchings
AU - Chenghua Liu
AU - Boning Meng
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2610.26803
UR - https://arxiv.org/abs/2610.26803
AB - 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 and controlling the resulting error terms. This avoids the auxiliary vertices and tree constructions used in the original proof. The argument preserves the required parameter bounds and yields the same FPRAS guarantee.
ER -