Perfect matchings: approximate counting and entropy

Source and verification

This article explains family 113 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Perfect matchings and relative approximation

A perfect matching of a finite undirected graph uses exactly one edge at each vertex. Write $Z(G)$ for the number of perfect matchings. Finding one matching and counting all matchings are different tasks; sampling all matchings, regardless of size, does not automatically estimate the possibly tiny perfect-matching contribution.

A fully polynomial randomized approximation scheme, or FPRAS, returns $\hat{Z}$ satisfying

$$\begin{array}{rl}& \mathrm{Pr}[(1-\epsilon )Z\le \hat{Z}\le (1+\epsilon )Z]\\ & \ge 1-\delta ,\end{array}$$

in time polynomial in the input length, ${\epsilon }^{-1}$, and $\log ({\delta }^{-1})$. This is a relative-error statement, so the zero-count case requires particular care.

Counting manuscript statement

There is a uniform FPRAS for perfect matchings in every finite simple undirected graph. It returns zero on every execution when no perfect matching exists, and has a polynomial bit-time bound on every random tape, including unsuccessful ones. The stated parameter range is $0<\epsilon <1$ and $0<\delta <1/2$. (OpenAI, 2026)

The input need not be bipartite or dense. The second manuscript in the family studies entropy at prescribed matching marginals and a different, coarser deterministic approximation. Those estimates should not be confused with the FPRAS.

🏷️ Weighted laws and an annealing identity

Give each edge a positive activity $w_e$ and each perfect matching weight ${\prod }_{e\in M}{w}_e$. The partition function is the sum of these weights. Its normalized weights define a probability law.

The counting proof begins with a complete graph, whose perfect-matching count on $2m$ vertices is $(2m-1)(2m-3)\cdots 1$, then gradually suppresses edges absent from $G$. For neighboring weight systems, the ratio of partition functions is an expectation under the earlier law:

$$\frac{Z(w^{\prime })}{Z(w)}={\mathbb{E}}_w\prod _{e\in M}\frac{w_e^{\prime }}{w_e}.$$

Multiplying estimated neighboring ratios recovers the final count from the known initial one. The proof must control accumulated error, residual weight from suppressed edges, and the cost of obtaining the samples.

Vertex scaling preserves the matching law. If $w_{uv}$ is multiplied by $a_u{a}_v$, every perfect matching gains exactly the common factor ${\prod }_v{a}_v$, because it meets every vertex once. This allows the source to balance local quantities without changing normalized probabilities. The required scales are learned from two-hole partition ratios, obtained by deleting pairs of vertices.

🏷️ Auxiliary graphs and a larger sampling space

The manuscript replaces logical edges by weighted paths and adds weak auxiliary clique edges in overlapping tree-indexed bags. Under its balance condition, the new partition function is at most twice the real-path partition function. Consequently a sample uses only real edges with probability at least one half; conditioning on that event recovers the intended law. Marked auxiliary edges expose the two-hole ratios needed for later balancing.

The inflation estimate uses pairing capacities for even hole sets, measured through bottleneck paths. Subdivision transfers the capacity bound and regularizes incident strengths. These estimates pay for added states rather than assuming their mass is small.

The sampler operates on a product of perfect-matching spaces, using local switches and exchanges of alternating cycles between matching coordinates. Its initial energy estimate controls only additive functions of two coordinates. An exact signed identity for a whole-cycle difference is not itself a path of legal chain moves: some terms change many edges. Separate encodings compare those terms to legal switches with bounded multiplicity.

A ladder of nearby activity laws and many replicas at each tier extends the energy estimate to arbitrary product-space functions. Orthogonal decomposition assigns each interaction term to at most one pair, and replication makes the remaining contribution absorbable. This is the step giving a full spectral-gap estimate, rather than just bounds for a restricted class of observables.

The sampler stays defined with the same time cap after an inaccurate empirical estimate. Balance is used to prove that accurate estimates propagate, not as an unchecked precondition that might make a bad random run hang. An initial exact matching-existence test handles $Z=0$.

🏷️ Entropy at a prescribed marginal vector

For the entropy companion, parallel edges are allowed and distinguished; loops are excluded. On a graph with $2m$ vertices, let $P(G)$ be the convex hull of perfect-matching incidence vectors. A point $x\in P(G)$ is exactly a feasible vector of edge-inclusion probabilities.

Among all matching laws with those marginals, define maximum entropy

$$H(x)=\underset{p}{\max }\left(-\sum _M{p}_M\log p_M\right).$$

The maximum is over laws satisfying ${\sum }_{M\ni e}{p}_M=x_e$. Also put

$$\begin{array}{rl}F(x)& =-\sum _e{x}_e\log x_e,\\ B(x)& =-\sum _e(1-x_e)\log (1-x_e),\end{array}$$

with natural logarithms and $0\log 0=0$. These are explicit coordinate sums, while $H(x)$ concerns an entire joint distribution.

Entropy manuscript statement

For every feasible $x$ on a loopless multigraph with $2m\ge 2$ vertices,

$$\begin{array}{c}H(x)\le F(x),\\ \begin{array}{rl}& F(x)-H(x)\\ & \le (2-2/m)B(x).\end{array}\end{array}$$

Boundary points of the polytope are included. For $m=1$, the equality $H=F$ is exact. The empty graph has one empty matching and zero entropy, handled separately. (OpenAI, 2026b)

The upper bound follows from Shearer’s inequality. At each vertex, a matching chooses one incident edge, so the entropy of that local choice is $-{\sum }_{e\ni v}{x}_e\log x_e$. Every edge coordinate occurs in two such vertex stars. Halving the sum of star entropies gives $F(x)$.

🏷️ From pointwise entropy to a counting estimate

The inequality $-(1-u)\log (1-u)\le u$ for $0\le u\le 1$ implies $B(x)\le {\sum }_e{x}_e=m$. Hence the lower entropy bound gives

$$\begin{array}{rl}& F(x)+B(x)\\ & \le H(x)+(3-2/m)B(x)\\ & \le \log Z(G)+3m-2.\end{array}$$

For the marginal vector of the uniform matching law, its entropy is $\log Z(G)$ and the upper bound yields $\log Z(G)\le F(x)\le F(x)+B(x)$. Therefore

$$\begin{array}{c}\Phi =\underset{x\in P(G)}{\max }(F(x)+B(x)),\\ 0\le \Phi -\log Z(G)\le 3m-2.\end{array}$$

An additive error proportional to $m$ in the logarithm corresponds to an exponential factor in the count. It is not arbitrarily small relative error. The companion implements a deterministic bit algorithm returning an integer $A$ with

$$Z(G)/512^n\le A\le Z(G),$$

where $n$ is the number of vertices and multiplicities may be supplied in binary. It does not expand those multiplicities into individual edges. A separate singleton-loop convention, where a loop covers one vertex, has factor $2^{18n}$ and rational output. (OpenAI, 2026b)

🏷️ Face geometry and covariance

Let $F_x$ be the smallest face of $P(G)$ containing $x$, and retain only coordinates with $x_e>0$. The entropy paper’s geometric input is

$$|\mathrm{supp}x|-\dim F_x\le 3m-2.$$

Tight odd-cut equations describe the relevant constraints. Contracting a tight cut gives two smaller faces. Their crossing-edge coordinates must agree, but each direction’s crossing-coordinate sum is already zero. Matching them therefore costs at most $|C|-1$ independent conditions, rather than $|C|$. This saved condition closes the sharp induction.

The maximum-entropy law on a face has exponential weights, and the Hessian of its log-partition function is a covariance matrix. Its image is the face’s direction space. The proof varies exponential tilts inside that space, avoiding inversion of a singular ambient covariance matrix or differentiation across faces.

At a hypothetical positive maximum of $F-cB-H$, first-order stationarity removes acceleration terms from second derivatives. Summing the remaining inequalities over positive covariance eigenvalues contradicts the face-dimension estimate when $c>2-2/m$. Taking the endpoint gives the claimed coefficient. The scope page documents the entropy conclusion and a triangle-expansion face correspondence, but not the paper’s full global face-dimension bound as a selected comparator statement.

🏷️ Uniform marginal examples

Suppose there are $k\ge 2$ edge-disjoint perfect matchings. Their uniform mixture has $x_e=1/k$ on $mk$ edges. Substitution gives

$$\begin{array}{rl}F(x)& =m\log k,\\ B(x)& =-m(k-1)\log (1-1/k).\end{array}$$

Since $\log Z(G)\ge H(x)$, the entropy claim implies

$$Z(G)\ge k^m(1-1/k{)}^{2(m-1)(k-1)}.$$

The weaker estimate $Z(G)\ge e^{-2(m-1)}{k}^m$ follows from $(k-1)\log (1-1/k)\ge -1$. Its usefulness depends on the degree scale; it need not beat stronger specialized estimates for small fixed degree.

🏷️ Key steps and proof outlines

Relative errors must be budgeted across annealing stages

Write $r_i=Z(w_{i+1})/Z(w_i)$ for successive partition-function ratios. Their product telescopes, so $Z(w_{\ell })=Z(w_0){\prod }_{i<\ell }{r}_i$. If every estimate has relative error at most $\eta$, the final multiplicative error lies between $(1-\eta {)}^{\ell }$ and $(1+\eta {)}^{\ell }$. For $0<\eta \le 1/2$, taking logarithms bounds its magnitude by $2\ell \eta$. Thus one chooses per-stage accuracy proportional to $\epsilon /\ell$, not simply $\epsilon$.

The same bookkeeping applies to failure probabilities: allocate a failure budget summing to at most $\delta$ over all ratio and balance estimates. Approximate samples introduce another expectation error bounded by total variation times the observable’s range. The source’s balancing and inflation bounds keep the relevant acceptance probabilities and ratio observables under control. Without such control, a polynomial spectral gap alone would not guarantee a polynomial relative-error estimator for a rare event. (OpenAI, 2026a)

The larger sampler must also mix arbitrary observables. Its initial two-coordinate energy estimate only handles a restricted class of functions. The replica ladder and orthogonal decomposition distribute higher-order interactions among pairs and absorb the remaining error. This is the logical place where a full spectral-gap theorem enters the counting pipeline; a proof for additive observables cannot be substituted for it.

The entropy contradiction is a covariance trace calculation

The companion’s “Entropy and the covariance trace” makes the lower bound a second-variation argument. Work on the minimal face containing a strictly fractional marginal vector $x$. The maximum-entropy law has probabilities proportional to $\exp (\theta \cdot a)$, where $a$ runs over matching incidence vectors on that face. Its covariance matrix is

$$K=\mathbb{E}[(a-x)(a-x{)}^{\mathsf{T}}].$$

Positive probability on every face atom implies that the image of $K$ is the face’s direction space, of dimension $d$. In particular, no inverse of a singular ambient covariance matrix is needed. (OpenAI, 2026b)

Let $J_c=F-cB$ and suppose $J_c-H$ has a local maximum. Tilt the law by replacing $\theta$ with $\theta +tv$. The mean curve $y(t)$ satisfies $y^{\prime }(0)=Kv$. Its acceleration stays in the same face direction space. First-order stationarity therefore cancels the acceleration term in the second derivative. If $D$ is the diagonal Hessian of $J_c$, the result is

$$0\ge (Kv{)}^{\mathsf{T}}D(Kv)+v^{\mathsf{T}}Kv.$$

Take positive covariance eigenvectors, divide each corresponding inequality by its eigenvalue and sum. This yields $0\ge d+\mathrm{tr}(KD)$. The diagonal entries are

$$K_{ee}=x_e(1-x_e),D_{ee}=-1/x_e+c/(1-x_e).$$

Since ${\sum }_e{x}_e=m$ and there are $s$ supported edges, $\mathrm{tr}(KD)=-s+(c+1)m$. Thus a local maximum forces $0\ge d-s+(c+1)m$.

Boundary reduction and the sharp endpoint

The geometric theorem supplies $d\ge s-3m+2$. To use it at a maximum, first delete zero-marginal edges and remove endpoints of value-one edges. These operations preserve the three entropy expressions and leave only strictly fractional coordinates. If the original graph has $2M$ vertices, the reduced graph has $2m$ vertices. An empty reduction has $F=B=H=0$ and cannot carry the assumed positive maximum; consequently $1\le m\le M$ when this geometric bound is applied.

Choose $c=2-2/M+ϵ$ with $ϵ>0$. Combining the trace and dimension bounds gives

$$0\ge 2+(c-2)m=2(1-m/M)+ϵm>0,$$

a contradiction to any positive maximum. Letting $ϵ\downarrow 0$ establishes the sharp coefficient. The strict auxiliary slack is essential: at the endpoint itself the geometric inequalities can be equalities, so the same contradiction would disappear. Continuity of maximum entropy on the finite matching polytope justifies taking maxima and passing to boundary points.

See Also

• Common-base counting uses defect states and trace mixing; bipartite perfect matchings form a special case of two partition matroids.
• Contingency tables distinguishes uniform sampling, expected-time exactness, and bounded-time relative counting.
• Permanent representations studies exact polynomial representations, rather than randomized approximation of a nonnegative count.

🏷️ Manuscripts and verification scope

• A Fully Polynomial Randomized Approximation Scheme for Perfect Matchings in General Graphs — pinned manuscript and companion source.
• Entropy and Face Dimension of the Perfect-Matching Polytope — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The page includes the FPRAS, pointwise entropy inequalities, and deterministic exponential-factor counts. Its geometric comparator covers face correspondence under triangle expansion, not the full sharp global face-dimension theorem used in the manuscript. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026a. A Fully Polynomial Randomized Approximation Scheme for Perfect Matchings in General Graphs.

🐻  OpenAI 2026b. Entropy and Face Dimension of the Perfect-Matching Polytope.