Approximate counting and entropy of perfect matchings

1 · The essentials

A perfect matching is a choice of connections that pairs every vertex with exactly one other vertex. This family of manuscripts studies how to count these choices and how much uncertainty a random choice among them can have. The counting manuscript describes a randomized algorithm for arbitrary finite simple undirected graphs. If no perfect matching exists, the algorithm always returns zero. Otherwise, it estimates the count with a chosen relative accuracy and a chosen upper limit on the chance of failure, within the stated polynomial running time. The companion manuscript bounds uncertainty when the probability of using each connection is fixed, including cases where some connections are always or never used. The entropy companion has a Lean formalization; the supplied source does not identify the counting algorithm as formalized.

A picture to help (an imperfect image, not to be taken literally)

As an imperfect image, imagine pairing everyone at a gathering, where only certain pairs are allowed. One question asks how many complete pairing plans are possible; another asks how unpredictable the chosen plan can be when each allowed pair has a prescribed chance of appearing.

Why it matters

The counting manuscript describes its algorithm as resolving the general-graph perfect-matching approximation problem. Its guarantee distinguishes an exact answer when the count is zero from a controlled approximation when the count is positive. The entropy companion proves the stated conjecture of Anari, Oveis Gharan, and Vinzant, with bounds that also cover the boundary of the feasible set.

2 · Going further

The counting problem takes an arbitrary finite simple undirected graph and asks for its number of perfect matchings. Manuscript 1 presents a fully polynomial randomized approximation scheme (FPRAS): when the count is positive, its relative error is at most $ε$ with failure probability at most $δ$ . Its worst-case bit running time is polynomial in the input length, $ε^{- 1}$ , and $lo g δ^{- 1}$ . When no perfect matching exists, it returns zero with certainty. These are the guarantees shown in the manuscript; no counting formalization is specified in the source.

The entropy problem concerns a loopless labelled multigraph on $2 m \geq 2$ vertices. A feasible vector $x$ specifies edge-use probabilities arising from some probability distribution over perfect matchings. Let $H (x)$ be the maximum entropy among all such distributions with those marginals. The Lean-formalized companion gives $F (x) - (2 - 2/ m) B (x) \leq H (x) \leq F (x)$ , where $F (x) = - \sum_{e} x_{e} lo g x_{e}$ and $B (x) = - \sum_{e} (1 - x_{e}) lo g (1 - x_{e})$ . The bound applies throughout the perfect-matching polytope, including its boundary.

The same companion gives the sharp geometric bound $∣ supp x ∣ - dim F_{x} \leq 3 m - 2$ , where $F_{x}$ is the minimal face containing $x$ . Thus the family brings together approximate counting, entropy at fixed edge probabilities, and the geometry of feasible probabilities. The supplied abstracts state the results but do not describe the algorithm or the main steps of either argument, so they do not establish how the entropy result is used, if at all, in the counting manuscript.

Useful notions

Graphs and perfect matchings
Probability distributions and edge-use probabilities
Relative error and failure probability
Entropy
Polytopes and their faces

What was known before / what is new

Before

The source identifies a general-graph perfect-matching approximation problem and describes the counting manuscript as resolving it. It also identifies the perfect-matching entropy conjecture of Anari, Oveis Gharan, and Vinzant. It supplies no further history or earlier bounds.

New

Manuscript 1 presents an FPRAS for arbitrary finite simple undirected graphs, with exact detection of zero counts and the stated worst-case bit-time guarantee. Manuscript 2 proves the entropy inequality for every feasible marginal vector in the specified multigraph setting, including boundary points. It also gives the sharp support-versus-face-dimension bound.

Limits and assumptions

The counting guarantee is for finite simple undirected graphs; the entropy and face-dimension statements concern feasible perfect-matching marginals in loopless labelled multigraphs on $2 m \geq 2$ vertices. For positive counts, the algorithm offers a probabilistic approximation rather than an exact count. The explicitly identified Lean formalization is Manuscript 2, the entropy and face-dimension companion; it should not be taken as verification of the counting algorithm. The abstracts do not specify finer-grained formalization coverage, argument details, or further open questions.

Mini glossary

Perfect matching: A set of edges in which every vertex belongs to exactly one selected edge.
FPRAS: A randomized approximation scheme with controlled relative error and failure probability, and the polynomial running-time guarantee stated above.
Edge marginal: The probability that a particular edge appears in a randomly selected perfect matching.
Entropy: A measure of uncertainty in a probability distribution, here over perfect matchings.
Perfect-matching polytope: The set of feasible vectors of edge marginals for probability distributions over perfect matchings.
Support: The set of edges whose coordinates in the marginal vector are positive.

Keywords : Perfect matchings · Approximate counting · Entropy

AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.

3 · Technical details and sources

Claim made in the manuscript (source text)

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.

Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.

Scope of the Lean formalization (source text)

…

lean/docs/113.md

Manuscripts in this family

★

A Fully Polynomial Randomized Approximation Scheme for Perfect Matchings in General Graphs

23/09/2026

To be verified

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, $ε^{- 1}$ , and $lo g δ^{- 1}$ .

PDF GitHub folder

Entropy and Face Dimension of the Perfect-Matching Polytope

23/09/2026

Verified by Lean

We prove the perfect-matching entropy conjecture of Anari, Oveis Gharan, and Vinzant. For every feasible vector x of perfect-matching edge marginals in a loopless labelled multigraph on $2 m \geq 2$ vertices, the maximum entropy $H (x)$ of a matching law with marginals x satisfies $F (x) - (2 - 2/ m) B (x) \leq H (x) \leq F (x),$ where $F (x) = - \sum_{e} x_{e} lo g x_{e}$ and $B (x) = - \sum_{e} (1 - x_{e}) lo g (1 - x_{e})$ . This bound holds throughout the polytope, including its boundary. We also prove the sharp bound $∣ supp x ∣ - dim F_{x} \leq 3 m - 2$ , where F_x is the minimal face of the perfect-matching polytope containing x.

PDF GitHub folder Lean formalization