Approximate counting and entropy of perfect matchings

← All digests

Family 113 · Theoretical computer science
Importance 4/5 · Provisional editorial rating
Sources consulted 2026-10-09

Finding one way to pair every vertex of a graph is very different from counting all such pairings. Family 113 brings together two claims about this gap: a randomized approximation scheme for the number of perfect matchings in any simple graph, and an entropy inequality describing how much randomness a matching distribution can retain when its edge probabilities are fixed.

1. The question

A graph has vertices and edges joining pairs of vertices. A perfect matching chooses edges so that every vertex belongs to exactly one chosen edge. One may think of pairing participants when edges specify compatible pairs.

An existence algorithm can answer whether a complete pairing is possible and return one. Counting asks how many different complete pairings exist. The answer can be exponentially large, even when finding one is easy.

The algorithmic question is whether that count can be estimated efficiently to any prescribed relative accuracy, without restricting the graph to a special class.

The entropy question starts from local data: the probability that each edge is chosen. How much uncertainty can remain about the whole matching? Local probabilities do not specify a joint distribution, because selected edges must cooperate to cover every vertex exactly once.

2. Background and essential definitions

Perfect matchings and relative approximation

Write $\mathcal M(G)$ for the perfect matchings of a graph $G$, and

$$Z(G)=|\mathcal M(G)|.$$

An estimate has relative error at most $\varepsilon$ when it lies between $(1-\varepsilon)Z(G)$ and $(1+\varepsilon)Z(G)$. A ten-percent estimate of a million matchings may differ by a hundred thousand; the same requirement near a small count is much stricter.

A fully polynomial randomized approximation scheme, or FPRAS, produces such an estimate with probability at least $1-\delta$, in time polynomial in input length, $\varepsilon^{-1}$, and $\log(1/\delta)$. Here $\delta$ is the allowed failure probability.

When the count is zero, a multiplicative guarantee needs special attention. The manuscript explicitly tests existence and returns zero with certainty in that case.

Marginals and entropy

For a probability distribution $p$ on matchings, the marginal $x_e$ is the probability that edge $e$ belongs to the chosen matching. The entropy is

$$\operatorname{Ent}(p)=-\sum_{M\in\mathcal M(G)}p_M\log p_M,$$

using natural logarithms and the convention $0\log0=0$. Entropy measures uncertainty: it is zero for a fixed matching and equals $\log Z(G)$ for the uniform distribution.

Not every vector of numbers in $[0,1]$ is a feasible vector of marginals. At each vertex, incident-edge probabilities must sum to one. In general graphs, odd subsets impose further constraints: a perfect matching must cross the boundary of any odd vertex set at least once.

The perfect-matching polytope is the set of feasible marginal vectors, equivalently the convex hull of matching indicator vectors. A convex hull consists of all weighted averages with nonnegative weights summing to one.

For a feasible vector $x$, let $H(x)$ be the maximum entropy among distributions having those marginals. This is a constrained optimization over whole matching distributions.

3. Development history and previous partial results

Edmonds’s 1965 matching algorithm established polynomial-time optimization in general graphs. His polytope theorem also identified the odd-cut constraints that distinguish general matching from its bipartite counterpart.

Valiant showed that exact counting is computationally difficult even for bipartite perfect matchings, through the permanent of a zero–one matrix. Bipartite means that vertices split into two parts and every edge crosses between them. Planar graphs admit special exact counting techniques based on Pfaffians, but arbitrary graphs need a different approach.

Jerrum and Sinclair developed efficient randomized approximation for counting all matchings, summed over every possible cardinality. Their perfect-matching result required control of the ratio between near-perfect and perfect matchings. Counting all matchings does not automatically isolate the potentially rare perfect ones accurately.

Jerrum, Sinclair, and Vigoda removed this obstruction for bipartite graphs, giving an FPRAS for nonnegative permanents. Their method balances near-perfect configurations according to the vertices left unmatched.

Extending that particular chain to general graphs faces a documented obstacle. Štefankovič, Vigoda, and Wilmes constructed instances where the specified family of perfect-and-near-perfect chains either mixes slowly or assigns too little mass to perfect matchings. This leaves room for a different state space, rather than proving approximate counting impossible.

On the entropy side, bipartite inequalities of Schrijver and Gurvits give strong comparisons with edgewise expressions. Anari, Oveis Gharan, and Vinzant proposed an entropy-optimization approach for general matching and a linear-error conjecture, cited precisely in M2. The odd-cut geometry makes the general case different.

4. What the new manuscripts claim

M1 claims an FPRAS for perfect matchings in every finite simple undirected graph:

$$\Pr\!\left[(1-\varepsilon)Z(G)\le\widehat Z\le(1+\varepsilon)Z(G)\right]\ge1-\delta.$$

It returns a nonnegative rational estimate, detects a zero count exactly, and has a polynomial bit-time bound on every execution. Its consequences include counting matchings of a prescribed size and edge subsets with prescribed vertex degrees, together with almost-uniform feasible sampling.

M2 treats loopless labeled multigraphs on $2m$ vertices, where parallel edges count as distinct choices. Define

$$F(x)=-\sum_e x_e\log x_e, \qquad B(x)=-\sum_e(1-x_e)\log(1-x_e).$$

For every feasible marginal vector, including boundary points, it claims

$$F(x)-\left(2-\frac2m\right)B(x)\le H(x)\le F(x).$$

Boundary points allow some edge probabilities to equal zero or one. They cannot be discarded as pathological: forced and forbidden edges occur naturally.

Optimizing the edgewise binary entropy yields the consequence

$$\log Z(G)\le\max_x\{F(x)+B(x)\}\le\log Z(G)+3m-2.$$

M2 also supplies a deterministic polynomial-bit-time approximation within factor $512^n$ for graphs with binary-encoded edge multiplicities, where $n$ is the vertex count. This much coarser guarantee is distinct from M1’s arbitrarily accurate randomized scheme.

5. Why the advance matters

Importance: 4/5, provisional. General-graph perfect-matching approximation is a central counting problem. The claimed algorithm would close a major gap between bipartite and unrestricted graphs without requiring density or other structural promises.

The entropy statement offers a complementary kind of understanding. It relates the global diversity of feasible matchings to quantities computed from individual edge probabilities. Such inequalities connect combinatorial counting, convex optimization, and probability.

The family should not be read as making exact counting easy. Relative approximation permits controlled numerical error and, for M1, a small failure probability. Exact counting asks for every digit of the integer answer and remains a different computational task.

The two manuscripts also illustrate that a structural inequality can be useful even when it alone produces only an exponential-factor approximation. Its value includes count lower bounds and geometric information, not just the strongest algorithmic guarantee elsewhere in the family.

6. The main idea

Count by multiplying manageable ratios

M1 starts with a complete graph, whose perfect-matchings count is known, and gradually suppresses edges absent from the target graph. Each stage has a weighted sum of matchings, called its partition function.

If consecutive partition functions have ratios that can be estimated accurately, multiplying those estimates recovers the final count. This process is often called annealing. Its success depends on drawing useful samples from every intermediate distribution.

Change the sampling space

Rather than directly reuse the obstructed perfect-and-near-perfect chain, the manuscript enlarges the graph. Logical edges become weighted paths, and auxiliary edges connect vertices inside organized bags.

The construction controls the extra probability mass introduced by those auxiliary edges. Under the required balance, a sampled matching uses only the real path edges with probability at least one half. Such an event recovers a matching of the logical graph.

Marked auxiliary edges also expose ratios involving two unmatched vertices. Those observations update the balance conditions used in later counting stages.

The sampler works with several matching coordinates at nearby weight levels. It exchanges alternating cycles between coordinates: when two matchings are overlaid, their differing edges form alternating cycles along which assignments can be swapped. Replication across levels helps control variation that a two-coordinate estimate alone would miss.

The manuscript separately bounds random-bit use and arithmetic sizes, so inaccurate statistical estimates do not create an unbounded running-time path.

Entropy through the geometry of feasible means

M2 studies the smallest face of the matching polytope containing $x$. A face records constraints that are tight throughout the relevant portion of the polytope; its dimension counts the remaining independent directions of variation.

The paper claims the sharp geometric estimate

$$|\operatorname{supp}x|-\dim F_x\le3m-2,$$

where $\operatorname{supp}x$ is the set of positive coordinates and $F_x$ is the minimal face. Here $F_x$ denotes a geometric face, distinct from the scalar function $F(x)$.

Maximum-entropy distributions have an exponential-weight form on the matchings permitted by that face. Their covariance matrices describe how marginals respond to small changes in weights. The argument compares second derivatives of a proposed entropy deficit with the face-dimension estimate. A positive deficit beyond the claimed bound would violate that geometric constraint.

Working inside the minimal face lets the argument include boundary marginals without pretending the ambient covariance matrix is invertible.

7. Scope, limitations, and open questions

M1’s headline input is an unweighted simple graph. M2’s entropy theorem permits distinguished parallel edges, and its deterministic algorithm handles binary multiplicities. These input conventions should stay attached to their respective guarantees.

The entropy coefficient cannot simply be replaced by the stronger bipartite coefficient one: M2 gives a nonbipartite counterexample. Its geometric sharpness examples do not establish that every constant in the entropy comparison is optimal.

The polynomial exponents and constants in the counting constructions are large. The claims settle asymptotic feasibility rather than provide benchmarked sampling software. Faster implementations and sharper structural inequalities remain separate directions.

8. Sources and further reading

M1’s introduction distinguishes all-matchings counting, bipartite perfect-matchings counting, and general perfect-matchings counting. M2’s first two theorems separate the entropy inequality from its deterministic counting consequence. Reading these distinctions first avoids conflating their different approximation guarantees.

Source manuscripts

• M1. OpenAI, A Fully Polynomial Randomized Approximation Scheme for Perfect Matchings in General Graphs (September 23, 2026).
• M2. OpenAI, Entropy and Face Dimension of the Perfect-Matching Polytope (September 23, 2026).

Sources consulted on 9 October 2026 at repository revision fd4aeeb. Download the manuscript citations.