1 Introduction
Let G=(V,E) be a finite simple undirected graph. A perfect matching is a set of edges incident to each vertex exactly once. Write
A fully polynomial randomized approximation scheme approximates Z(G) within a prescribed relative error, with a prescribed success probability, in time polynomial in the input length and the reciprocal error. The confidence parameter enters through its logarithm. We prove the following theorem, including a bound on the time of every execution.
Theorem 1.1. There is a uniform classical randomized algorithm which, given G and rational parameters 0<\eps<1 and 0<\delta<1/2, returns a nonnegative rational number \widehat Z such that
If Z(G)=0, the output is zero with certainty. The worst-case bit running time is polynomial in the input encoding length, \eps^{-1}, and \log\delta^{-1}.
As consequences, Section 10 gives counting schemes for edge subsets with prescribed vertex degrees and for matchings of a specified size. On feasible inputs, its samplers always return a feasible object and approximate the corresponding uniform law in total variation.
1.1 History and significance
Perfect matchings illustrate the distinction between finding a combinatorial structure and counting its realizations. Edmonds gave a polynomial-time algorithm for finding a maximum matching in a general graph [Edmonds(1965)]. Valiant proved that exact counting is #P-complete even for bipartite graphs, where it is the permanent of a zero–one matrix [Valiant(1979)]. Pfaffian methods give polynomial-time exact counting for planar graphs [Kasteleyn(1963)].
For approximation, three problems must be distinguished: counting all matchings, counting bipartite perfect matchings, and counting perfect matchings in general graphs. Jerrum and Sinclair gave an FPRAS for the total number of matchings in an arbitrary graph, summed over all cardinalities [Jerrum and Sinclair(1989), Corollary 4.5]. Their perfect-matching algorithm applied when the ratio of near-perfect matchings, which leave exactly two vertices unmatched, to perfect matchings was bounded by a fixed polynomial [Jerrum and Sinclair(1989), Theorem 5.3]. Without such a bound, perfect matchings can carry too little stationary mass for this sampling approach. Approximating the total number of matchings therefore does not isolate its perfect-matching contribution with relative accuracy.
Jerrum, Sinclair, and Vigoda removed the ratio restriction in the bipartite setting and obtained an FPRAS for the permanent of every nonnegative matrix [Jerrum et al.(2004)Jerrum, Sinclair, and Vigoda, Theorem 1.1]. Their method assigns weights to near-perfect states according to their two unmatched vertices and learns suitable weights while gradually changing edge activities. The general-graph question was explicitly raised by Jerrum and Sinclair [Jerrum and Sinclair(1989), Section 7(i)] and remained a benchmark for approximate counting. Cai and Liu relate it to approximation for the eight-vertex model [Cai and Liu(2020)]; Fei, Goldberg, and Lu distinguish the spin-system parameter line equivalent to general perfect-matching approximation from the region covered by their FPRAS [Fei et al.(2025)Fei, Goldberg, and Lu, Proposition 1.2 and Theorem 1.5]. Remark 1.1 answers the general-graph perfect-matching approximation problem affirmatively.
A direct extension of the bipartite chain faces a precise obstruction. Štefankovič, Vigoda, and Wilmes constructed graphs on which every JSV-type chain has either exponentially small stationary probability of perfect matchings or exponentially slow mixing, even with arbitrary weights depending on the hole pattern [Štefankovič et al.(2018)Štefankovič, Vigoda, and Wilmes, Definition 2.1 and Theorem 2.2 in the full version]. Here JSV type means the perfect-and-near-perfect state space with the specified Broder proposals and a Metropolis acceptance rule. The sampler below uses a different state space: a product of perfect-matching spaces on an enlarged colored graph, with exchanges of alternating cycles between coordinates. Its energy comparison is proved for these states and moves.
Subsequent permanent algorithms sharpen the bipartite result. Bezáková, Štefankovič, Vazirani, and Vigoda accelerated the cooling schedule and improved the analysis of the matching chain [Bezáková et al.(2008)Bezáková, Štefankovič, Vazirani, and Vigoda]. Chen, Vigoda, and Yang obtain a further improvement through restricted Poincaré inequalities and coupled flows [Chen et al.(2026b)Chen, Vigoda, and Yang]; Chen, Guo, Vigoda, and Yang develop an energy-weighted multicommodity-flow comparison and improve the running time again [Chen et al.(2026a)Chen, Guo, Vigoda, and Yang]. These results concern bipartite perfect matchings.
For nonbipartite graphs, Yi gives deterministic relative approximation for hafnians, the weighted sums over perfect matchings, when the n-vertex support has minimum degree at least (1/2+\gamma)n and nonzero weights lie in [\theta,1] [Yi(2026), Theorem 1.1]. Here 0<\gamma<1/2 and 0<\theta\le1 are fixed constants, and the polynomial running-time exponent may depend on them. Remark 1.1 has no density promise on its simple unweighted input.
The proof below also builds on the methodological framework of weighted matching chains. Alternating overlays and weight-preserving switches underlie the encodings of Jerrum and Sinclair and of Jerrum, Sinclair, and Vigoda [Jerrum and Sinclair(1989), Jerrum et al.(2004)Jerrum, Sinclair, and Vigoda]. Their sampling-to-counting strategy learns local partition ratios while gradually changing activities. Here these ratios are exposed by marked edges in an enlarged graph, and vertex scaling maintains a row-wise balance condition. The capacity bound, subdivision and marked-edge identities needed for this construction are proved explicitly.
Energy comparison through weighted demands has classical antecedents in multicommodity-flow bounds for mixing [Sinclair(1992)]. Our comparison differs from routing every demand along a path of chain transitions: long-arc conversions enter a signed identity and need not be legal single updates. The resulting estimate initially controls only additive functions of two matching coordinates. The separate product-space argument is essential to obtain a spectral gap for arbitrary functions. It uses the classical orthogonal decomposition into coordinate interactions [Efron and Stein(1981), Section 2]; the ordered assignment of residual terms and the replication estimate are proved below.
1.2 Proof architecture
The counting algorithm starts with the complete graph, whose perfect matchings are easy to count, and gradually suppresses the nonedges of G by decreasing their positive activities. It estimates the ratios of successive partition functions and multiplies them. To keep the observations statistically useful, it updates vertex scales from estimates of the two-hole partition ratios: partition functions after deleting two vertices, divided by the current partition function. Accurate estimates keep each row maximum between two absolute constants. A vertex scale multiplies every complete matching weight by the same factor, preserving the probability law used to estimate the current counting ratio.
The purpose of balance is to control the extra mass introduced by an auxiliary graph. We replace each logical edge by a weighted path, with a bijection between logical perfect matchings and matchings using only these real path edges. We then add weak clique edges in overlapping bags indexed by a tree. Under balance, the added edges increase the partition function by at most a factor of two, so a sample uses only real edges with probability at least one half. A specially marked auxiliary edge exposes the corresponding two-hole partition ratio. These are exact event identities; they provide both the counting estimate and the data for the next scale update.
To prove the inflation bound, Remark 3.1 assigns a pairing capacity to each even hole set using the strongest bottleneck paths between its vertices. The capacity pays for the weights of possible added edges on those holes. Subdivision transfers this bound to the real graph while making incident effective strengths comparable. The resulting geometry supplies the tree of clique bags. Thus the hole estimates control the probability of the observable events, while the tree-bag structure supplies a sampler for their law.
That sampler uses local switches in one matching and exchanges alternating cycles between two matching coordinates. Its energy comparison initially controls only additive functions of the two coordinates. A quadrangulation adapted to the bag labels gives an exact signed identity for a whole-cycle difference (Remarks 5.1 and 6.1). The identity is not a route through chain transitions: long arc conversions may change many edges. Two-matching encodings instead compare its terms with local switches and cycle exchanges, with polynomially bounded multiplicity.
A ladder of nearby weight distributions then places many independent coordinates at each tier. An ordered orthogonal decomposition ensures that each coordinate-interaction term is charged to at most one pair. Replication reduces the coefficient of their combined contribution enough to absorb it. This yields a spectral gap for arbitrary functions of the product state (Remark 7.2). The bottom tier has unit activities and admits exact counting and ideal sampling by a tree dynamic program. The sampler requires no balance assumption. It therefore remains defined, with the same time bound, after an inaccurate empirical estimate; balance is used only to prove that accurate estimates propagate through the counting stages.
Table 1 summarizes the changes of law. Finally, Sections 8 and 9 account for all arithmetic and finite-bit random choices. Every polynomial has an absolute degree; the constants are chosen for transparent estimates rather than practical efficiency.
| Object | Vertices | Relation of matching laws |
| Input G | n | The target is its unweighted count Z(G). |
| Complete graph | n | Raw activities w^{(j)} gradually suppress the nonedges of G. |
| Vertex scaling | n | Activities \lambda preserve the normalized raw matching law. |
| Real paths | N | Subdivision gives a matching bijection with a common weight multiplier. |
| Colored bags | N | Their activities W recover the real law when every sampled edge is revealed as real. |
| Weight tiers | N | Common-interval clamps of W connect the unit-activity law to the bag law on one colored state space. |
Table 1: The successive graphs and probability laws. Here n is the original vertex count and N the enlarged count. Scaling, subdivision, conditioning, and clamping have distinct roles.
The specialized combinatorial and sampling arguments are proved here. We use Edmonds’s algorithm for the initial matching-existence test and Hoeffding’s bounded-variable inequality for concentration and confidence amplification [Edmonds(1965), Hoeffding(1963)].
2 Preliminaries
Logarithms are natural unless a base is indicated.
2.1 Weighted matchings and holes
We allow parallel edges distinguished by colors. A matching specifies the actual colored edges it uses. For positive rational activities a=(a_e), put
where H is the underlying graph and \calM(H-U) is its set of perfect matchings after deleting U. The empty graph has one perfect matching, of weight one. Whenever Z_a>0, define
These weighted colored graphs are intermediate spaces constructed from the simple input graph. Their representation is explicit: vertices, colored edges, and rational activities are stored individually. The main theorem retains the finite simple undirected input model; it does not assert a counting algorithm for compressed edge multiplicities or for singleton-covering loops.
We call the vertices in U holes. For distinct vertices we abbreviate g_a(\{i_1,\ldots,i_k\}) to g_a(i_1\cdots i_k). Collapsing parallel activities into their sum preserves every partition function. Conditional on a collapsed edge, its original type can be recovered with probabilities proportional to the summands.
The union of two matchings, with common edges retained twice, has maximum degree two. Its nontrivial components are alternating paths and even alternating cycles. Swapping the layers along a component preserves the product of their weights. In the union of two perfect matchings, deleting common identical edges leaves disjoint alternating cycles; different colors on the same pair of vertices form a cycle of length two. We fix a vertex order and a color order once and for all. They resolve every combinatorial tie in the proof.
2.2 Bottleneck similarities
For a positive weighted connected graph define
Simple paths suffice. This symmetric similarity satisfies B_{ij}\ge\min\{B_{ik},B_{kj}\}: concatenating two paths and erasing loops cannot lower their minimum activity. For t>1, its equivalence classes are the connected components of the graph retaining edges of activity at least t. Singletons are included. At t=1 we take one class containing every vertex, consistently with the floor at one. For an even set U define its pairing capacity
where \mathcal P runs over pairings of U. We use this quantity only in proofs; the counting algorithm never needs to enumerate pairings or compute \Phi_B(U) for a general hole set.
2.3 Tree bags
Definition 2.1. A tree-bag graph consists of a finite rooted tree of labels and a finite even vertex set. A label l at level k has height h_l=2^k; the root has level zero and a child has level one greater than its parent. Each vertex belongs to either one label or two adjacent labels. The bag at l is the set of vertices belonging to l. For each unordered pair of distinct vertices and each common label l, there is one edge of color l. There are no other edges. For an integer parameter D\ge1, its reference activities obey
We also consider activities obtained by clamping all W_e to one common interval [a,b]\subset(0,\infty).
Every vertex pair has at most two edge colors. At any bag, the interfaces with its parent and its different children are disjoint: a vertex in two such interfaces would have at least three memberships. Empty bags and repeated underlying vertex sets are permitted. Clamping is monotone and does not increase the ratio of a larger activity to a smaller one. In particular, reference activities of nearby labels remain comparable after clamping.
2.4 Dirichlet energy and approximation
For a finite reversible Markov kernel P with stationary law \mu, its Dirichlet energy is
A Poincaré inequality \Var_\mu f\le\gamma^{-1}\calE_{\mu,P}(f) means that the spectral gap is at least \gamma. A symmetric proposal Q has Metropolis acceptance probability [Metropolis et al.(1953)Metropolis, Rosenbluth, Rosenbluth, Teller, and Teller, Hastings(1970)] \min\{1,\mu(y)/\mu(x)\} for a proposed move from x to y. Its off-diagonal stationary capacity is
We regard inapplicable proposals as holding moves. All state spaces used below contain at least one perfect matching; thus their positive activities define probability laws with full support on that space.
Total variation is \|\mu-\rho\|_{\TV}=\frac12\sum_x|\mu(x)-\rho(x)|. A deterministic map, or a common randomized postprocessing kernel, does not increase total variation, by the triangle inequality. Two finite laws at total variation distance \eta admit a coupling that disagrees with probability \eta: first match the common masses \min(\mu(x),\rho(x)), then couple the remainders. Applying this construction successively bounds the discrepancy probability of an adaptive simulation by the sum of its conditional one-step errors.
3 Controlling the cost of unmatched vertices
This section proves the bound that will control the additional edges in our sampling graph. It uses only alternating paths and differentiation of a finite partition function.
Let V have even cardinality n\ge2, and give every edge of the complete logical graph K_V a positive activity \lambda_{ij}. Use the weighted matching notation of Section 2, abbreviating \calM(K_V-U) to \mathcal M(-U). For any positive activity array a on this graph, define the row maxima
The activities a are balanced if 1/4\le r_i(a)\le1 for every i. Let B be the bottleneck similarity of \lambda from (2.1), and let \Phi_B be its pairing capacity from (2.2).
The estimate we need controls every even hole set, although balance only bounds the two-hole ratios:
Theorem 3.1 (Logical hole bound). Let \lambda be balanced, let B be its bottleneck similarity, and set
For every even set U\subseteq V,
To prove this, we will add a small activity proportional to B_{ij} on every pair. Bounds for two and four holes keep the resulting partition inflation below two. Any pairing of an arbitrary hole set can then be inserted using the added edges, giving the stated bound.
We use two elementary alternating-path comparisons. Such weight-preserving overlays also underlie the weighted matching encodings in [Jerrum and Sinclair(1989), Jerrum et al.(2004)Jerrum, Sinclair, and Vigoda]; the comparisons and their constants needed here are proved below. In an overlay of two matchings, edges retain their layer. Common edges can be kept as two parallel copies. A path starting at a vertex unmatched in exactly one layer is then uniquely determined, and switching its edges between the layers preserves the product of their weights.
Lemma 3.2 (Four-hole inequality). For any positive activities \mu and four distinct vertices a,b,c,d,
Consequently, if every row maximum is at most 4, then
Proof. Overlay M\in\mathcal M(-\{a,b,c,d\}) and P\in\mathcal M(-\varnothing). The alternating path from a ends at one of b,c,d, say b. Switch that path between the layers. The output layers miss \{c,d\} and \{a,b\}, respectively, and their product weight is unchanged. This map is injective for the specified endpoint b: in the output overlay, follow the path from a and switch it back. The same argument applies to endpoints c,d. Summing the three injective comparisons and dividing by Z_\mu^2 proves the inequality. The remaining assertions follow immediately.
The four-hole comparison controls small hole sets by row maxima. We next need an additional factor when two holes are joined by a strong path. Normalizing by the row maximum at the moving hole will make the successive relocation errors add, without multiplying along the path.
The next lemma is stated with \mu\ge\lambda so that it continues to apply while we add activities to the graph. Its bottleneck similarity always remains the one defined from \lambda.
Lemma 3.3 (Relocating a hole along a strong path). Let B be defined by (2.1), and suppose that \mu_e\ge\lambda_e for every edge and
If |U|\in\{2,4\} and i,j\in U are distinct, then
Proof. Throughout this proof, omit the subscript \mu from g and r. Write B=B_{ij}. For B\le8, the assertion follows from (3.2). Suppose therefore that B>8, and choose a simple path from i to j whose \lambda-activities, and hence its \mu-activities, are all at least B.
We first give one step of the relocation. Let a be the hole currently on this path, let S be the current hole set, and let z be the next vertex. Thus a\in S and \mu_{az}\ge B. If z\in S, inserting az in a matching missing S is injective and increases its weight by \mu_{az}. Hence
The last inequality uses |S|\le4, (3.2), and r_a\ge1/8.
Now suppose z\notin S. Choose p\ne z with g(zp)=r_z. Inserting az gives g(az)\le1/\mu_{az}\le1/B<1/8, so p\ne a. Overlay M\in\mathcal M(-S) and P\in\mathcal M(-\{z,p\}). The path from a starts with an edge of P. Its endpoint belongs to exactly one of the following three cases.
- (i)
It ends at z. Switching the path gives layers missing S\setminus\{a\}\cup\{z\} and \{a,p\}. The product weight is unchanged.
- (ii)
It ends at p, which requires p\notin S. Switching gives layers missing S\setminus\{a\}\cup\{p\} and \{a,z\}. Insert az in the second layer, making it perfect. The product weight increases by \mu_{az}\ge B.
- (iii)
It ends at x\in S\setminus\{a,p\}. Switching gives layers missing S\setminus\{a,x\} and \{z,p,a,x\}. Insert az in the second layer; its remaining holes are \{p,x\}. Again the product weight increases by at least B.
These cases exhaust the possibilities. Indeed, the degree-one vertices in the overlay are exactly the symmetric difference of the two hole sets; if p\in S, then p is isolated and cannot be an endpoint of the path.
The edge az is absent from both input layers, since the first misses a and the second misses z. Switching cannot create an edge absent from the overlay. Each map is injective when its case and endpoint are specified. For case (i), the inverse switches the output path from a. For cases (ii) and (iii), first remove the inserted edge az from the second output layer, then switch the path from a in the resulting overlay. This reconstructs both input layers, including their common edges. Summing over all inputs, using g(ap)\le r_a, and dividing by Z_\mu^2r_z yields
An inapplicable first term inside the brackets is omitted entirely. The brackets are at most 96: for |S|=4 their first term is at most 48 and their at most three product terms are each at most 16; for |S|=2 the corresponding bound is 8. After division by r_a, therefore,
Starting at a=i, apply this recurrence along the chosen path, keeping all holes in U\setminus\{i\} fixed. Stop just before reaching the first of these fixed holes; such a hole exists because the path ends at j. The path is simple, so there are at most n-2 recurrence steps, followed by (3.4). The normalization by the current row maximum makes the leading terms telescope. Since r_i\le4,
as required.
Proof of Remark 3.1. Temporarily add a distinguished parallel edge of activity tB_{ij}/D_0 to every pair ij, where 0\le t\le1. Collapsing parallel edges gives activities
Write Z(t)=Z_{\mu(t)} and g_t=g_{\mu(t)}; B remains fixed. All partition functions involved are polynomials in t, and Z(t)>0. Differentiation of their finite sums gives
where sums over edges are unordered, and for distinct x,y,
On any initial time interval during which all row maxima belong to [1/8,4], Lemma 3.3 bounds every summand B_{ij}g_t(ij) and every summand B_{ij}g_t(xyij) by 10^5n. Since
we obtain, throughout that interval,
Integrating gives
For the lower row bound, fix a neighbor maximizing the row at time zero; the moving row maximum is at least this one evolving entry. Consequently, balance at time zero implies
Both bounds lie strictly inside [1/8,4]. By continuity, the row maxima cannot first leave this interval before time 1: at a proposed first exit the displayed strict bounds still hold and persist on a neighborhood. Thus all preceding estimates hold on [0,1], and
Choose a pairing Q of U attaining \Phi_B(U). At time 1, keep the original and added parallel edges distinguished. To each original matching in \mathcal M(-U), add the edges of Q using their added copies, of activities B_{ij}/D_0. This is an injective map into perfect matchings at time 1, and it multiplies every weight by \Phi_B(U)/D_0^{|U|/2}. Hence
Divide by Z(0)=Z_\lambda and apply (3.9).
4 A subdivision with controlled holes
The sampler will use additional clique edges. To control the mass these edges introduce, we first replace each logical edge by a path. The path profile has two roles: equal adjacent factors make the ratio of its two matching patterns telescope, and the gradual change from each endpoint to the middle makes incident effective strengths comparable. We first construct the enlarged graph and identify its marked laws, then bound the mass introduced by its additional edges.
Throughout this section the logical graph is the complete graph on an even number n\ge2 of vertices, with positive rational activities \lambda_{uv}\le4^K, where K\ge0 is an integer. Write B for its bottleneck similarity, and put
Here D_0=10^8(n+1)^4 is the constant in Remark 3.1. Thus 1\le B_{uv}\le H_u\le4^K.
4.1 The path profile
Orient each logical edge e=uv by the fixed vertex order, and replace it by a path
Internal vertices of different paths are distinct. Denote the activity of x_{j-1}x_j by t_j=t_j^e. For 1\le r\le p, set
We call these the real edges and write Z' and g' for their partition function and hole ratios. Let B' be their bottleneck similarity. The two innermost equal pairs have activity B_{uv}, because H_u2^{-(p-1)},H_v2^{-(p-1)}\le1/2.
Lemma 4.1. The real graph has N vertices. Its perfect matchings are in bijection with logical perfect matchings, and
On a noncentral real edge, its effective strength B' equals its activity. On the central edge of the path for uv, it equals B_{uv}. Incident effective strengths differ by a factor of at most two. For an internal vertex x_j, its maximum incident effective strength is
Its home terminal is u in the first case and v in the second. Every edge on its leg to its home has activity at least T_j.
Proof. An intact path has exactly two ways to match its internal vertices: the even-indexed edges, which use neither terminal, or the odd-indexed edges, which use both. The ratio of the latter weight to the former is \lambda_{uv}, since all the noncentral factors cancel in equal adjacent pairs. A real perfect matching therefore chooses the odd tiling precisely on a logical perfect matching. This proves the bijection and Equation (4.3).
Every noncentral edge has an equal-activity twin sharing an internal vertex of degree two. A path connecting its endpoints that avoids that edge must use the twin. Its bottleneck therefore cannot exceed the edge activity, and the direct edge attains that activity.
The minimum activity on the full path replacing e is \lambda_e. Consequently, for every t>1, real edges of activity at least t connect two terminals exactly when logical edges of activity at least t connect them: a simple path between terminals traverses complete subdivision paths. In particular B' restricted to terminals is B. Let a=x_{2p} and b=x_{2p+1} be the ends of the central edge. The legs from a,b to u,v have minimum activity B_{uv}. If B_{uv}>\max\{1,\lambda_{uv}\}, a logical path attaining B_{uv} avoids uv, and its subdivision together with these legs connects a to b with bottleneck B_{uv}. If B_{uv}=\max\{1,\lambda_{uv}\}, the central edge and the floor at one already give the lower bound. For the upper bound, any alternative path from a to b must first use an edge on a leg of activity B_{uv}. Thus B'_{ab}=B_{uv} in all cases.
Along each half of a path the displayed profile is nonincreasing toward the center and successive values differ by at most two. The effective strength at the center agrees with both innermost pairs. At a terminal u, every first edge has activity H_u. These facts give all remaining assertions.
4.2 The enlarged matching law
For each integer 0\le k\le\lfloor\log_2\max_uH_u\rfloor, take one label for every component of the enlarged graph whose retained edges have effective strength at least 2^k, including singleton components. A label at level k>0 has as parent its containing component at level k-1. At level zero there is one component; these labels therefore form a rooted tree. Components recurring at different levels are still different labels.
Label each real edge xy by the component containing it at level \lfloor\log_2B'_{xy}\rfloor. A vertex belongs precisely to the labels of its incident real edges. Equal-level incident labels are identical, and the factor-two bound in Remark 4.1 implies that there are at most two incident levels. If there are two, they are consecutive and their labels are parent and child. Thus these memberships satisfy Remark 2.1. In particular, a bag is the set of vertices with that membership; it need not be the entire threshold component defining its label.
Within every bag of label l and height h_l, add a virtual edge of activity h_l/D for each vertex pair. Collapse any real edge of color l into the virtual edge with the same endpoints and color, adding its activity. This gives one colored edge per common label, of activity
Since a real edge assigned to l has t_{xy}\le B'_{xy}<2h_l, these weights satisfy Equation (2.3). Also 1/D\le W_{xy,l}\le3\cdot4^K.
For each logical edge e, split off activity 1/D from the virtual activity on its central colored edge, and mark that portion as the probe for e. This is possible because h_l\ge1. After sampling a colored matching, independently reveal the portion of each used edge in proportion to its real, probe, and remaining virtual activities; zero portions are omitted.
Figure 1 shows the two real tilings and the probe on one illustrative path.
Figure 1: One subdivision path with K=1, p=4 and 4p+1=17 edges. The top labels are the real activities: H_u=4, H_v=B_{uv}=2, and \lambda_{uv}=1/2; the central edge has effective strength B'_{x_8x_9}=2. Solid edges show the selected real tiling. The even tiling uses neither terminal, and the odd tiling uses both; the odd-to-even weight ratio is \lambda_{uv}. The last row uses the probe portion of the central colored bag edge and real portions elsewhere. Here the central label has height h_l=2, so its collapsed activity 1/2+2/D consists of real activity 1/2, probe activity 1/D, and remaining virtual activity 1/D. The probe forces the real edges on the two outer legs to use both terminals. Their combined weight equals the even-tiling weight, so the remaining paths represent a logical matching with u,v deleted.
Let Z_{\mathrm{bag}} be the colored partition function of the enlarged graph, and put I=Z_{\mathrm{bag}}/Z'. This ratio measures the mass introduced by the auxiliary edges.
Proposition 4.2 (Marked matching laws). For arbitrary positive logical activities, sample from the bag matching law and reveal the edge portions as above. The all-real event has probability 1/I; conditional on this event, the decoded logical matching has law \pi_\lambda. For each logical edge uv,
Conditional on this event, the residual logical matching has the \lambda-weighted perfect-matching law on the vertices other than u,v.
Proof. Revealing portions recovers the weighted law before the real and virtual activities were collapsed. The all-real matchings have total weight Z'=C_0Z_\lambda, and their normalized law is transported to \pi_\lambda by Remark 4.1.
Now require the probe on the path for uv and real edges everywhere else. The probe matches x_{2p} to x_{2p+1}. The remaining vertices on its path have unique real tilings: the left one uses u, and the right one uses v. Equal adjacent activities in (4.2) show that their combined weight is exactly the even-edge baseline weight of this path. Other paths incident to u or v must use their even tilings. The remaining paths retain their even and odd alternatives, with ratio \lambda_e. Consequently these marked matchings are in bijection with logical matchings missing u,v, and every weight is multiplied by C_0/D. Their total mass is C_0 Z_\lambda(-uv)/D. Dividing by Z_{\mathrm{bag}}=IC_0Z_\lambda proves (4.4); the same constant weight multiplier proves the conditional-law assertion.
The identities show what the enlarged graph provides to the counting algorithm. To use its all-real event with polynomially many samples, we also need a uniform lower bound on that event’s probability. The next lower-bound estimate requires balance; the construction and the exact laws above do not.
Proposition 4.3 (Bounded inflation). If the logical activities are balanced, then
We prove this bound in the remainder of the section. A collection of virtual edges leaves a set U of endpoints to be removed from a real matching. Its added weight must therefore be compared with g'(U). The next two subsections transfer the logical hole estimate to these enlarged hole sets.
4.3 Exact accounting for deleted vertices
We next describe exactly what deleting internal vertices does to the logical graph. A path is broken if at least one of its internal vertices is deleted. Let E_{\mathrm{br}}(U) be the set of logical edges whose paths are broken by a hole set U.
Consider the ordered internal holes on a broken path. If a real completion exists, successive hole indices alternate in parity, because the intervening internal run must have even order. A first hole of even index forces the prefix to match the terminal u; we say that this hole consumes u and map it to u. A last hole of odd index similarly consumes and maps to v. Remove all consumed holes (zero, one, or two) from the list. The remaining holes split, in their order, into pairs (j,k) with j odd and k even; call these neutral pairs. There is no ambiguity when the list has one hole, since it cannot both have even and odd index.
Let R be the set of explicitly deleted terminals together with all consumed terminals. Feasibility requires these terminals to be distinct. To each consumed hole x_j assign the factor
For a neutral pair (j,k) assign
Let F=F(U) be the product of all these factors on all broken paths; an empty product is one. Both R and F depend only on U and the fixed path profiles, not on a choice of completion.
For a set E_0 of logical edges, write Z_\lambda(-R;E_0\text{ forbidden}) for the partition function after deleting R and forbidding those edges.
Lemma 4.4. If an even hole set U has a real completion, then R is even, |R|\le|U|, and
In particular, g'(U)\le F(U)g_\lambda(R).
Proof. Fix a broken path. A prefix ending immediately before a first hole of index j has j-1 internal vertices. If j is odd it uses the even tiling and leaves u unused; if j is even it uses the odd tiling and consumes u. The suffix has the analogous alternatives. Every run between consecutive holes has a unique tiling, since its order is even. These parity conditions prove the stated description of consumed holes and neutral pairs. On each path the number of consumed holes has the same parity as the number of internal holes. Adding explicit terminal holes gives |R|\equiv|U|\pmod2. Distinctness and |R|\le|U| follow from feasibility and the fact that each consumed terminal is charged to a different hole.
For completeness, all factors can be obtained from one prefix ratio. For even j, define
The profile gives
This is the factor for a first even-indexed hole consuming u; reflection gives the factor for a last odd-indexed hole consuming v. For a neutral pair (j,k), its shifted tiling relative to the even-edge baseline contributes
If j is odd on the left, its denominator is T_j; if j is odd on the right, its denominator is \lambda_e, also when j=2p+1. Substitution proves Equation (4.6). Prefixes and suffixes that do not consume a terminal, and runs outside these shifted intervals, retain their baseline even edges. Thus the product F accounts for all changes to the baseline on broken paths.
Every completion now determines a logical matching on the intact paths, using exactly the terminals outside R. Conversely, take any logical perfect matching on the vertices outside R that uses no broken edge. Give its selected intact paths their odd tilings, give other intact paths their even tilings, and fill all broken paths by the uniquely forced runs just described. The distinctness conditions ensure that no terminal is used twice or is both used and deleted. This reconstructs a real completion and is inverse to the first map. Its weight is C_0F times the logical weight, which proves Equation (4.7). Omitting the forbidden-edge condition and dividing by Equation (4.3) gives the inequality.
4.4 Charging the pairing capacity
The deletion identity gives a factor F(U) and a logical hole set R. To transfer the logical bound, we must compare the pairing capacity of U with that of R. The next lemma expresses both capacities through threshold classes. Throughout the comparison, these classes belong to the original undeleted graphs, so they are independent of the completion being counted.
Lemma 4.5 (Pairings in a hierarchy). Let B\ge1 be a symmetric similarity on a finite vertex set X, satisfying B_{ij}\ge\min\{B_{ik},B_{kj}\}. Let \mathcal C_t be the equivalence classes of B\ge t, including singletons. For every even set U\subseteq X,
There is one pairing that attains the maximum number of internal pairs in every threshold class simultaneously.
Proof. For any pairing Q,
Inside a threshold class C, there are at most \lfloor |C\cap U|/2\rfloor pairs of Q, proving the upper bound.
The threshold classes form a laminar family: any two are disjoint or one contains the other. Process its finitely many distinct classes from smaller to larger, starting with the singletons. In each class, pair its currently unpaired elements of U arbitrarily until at most one remains. When a class C has been processed, exactly \lfloor|C\cap U|/2\rfloor pairs lie inside it. Subsequent processing cannot create another pair inside C, because at most one element of C\cap U remains unpaired. The final class is X, and |U| is even, so the procedure produces a pairing. It attains every floor count, and therefore attains the integral upper bound.
Lemma 4.6. If the logical activities are balanced, then for every even set U of enlarged vertices,
More precisely, for every U with a real completion, the deterministic quantities above satisfy
Proof. The assertion is immediate if U has no completion, so suppose otherwise. For a threshold t>1 and any set A of enlarged vertices, let
where C ranges over the threshold classes of B'. Define S_t on logical vertices in the same way using B. These definitions make sense even when A has odd cardinality. The threshold partitions remain those of the undeleted graphs throughout this proof; only the sets of holes are changed.
By Remark 4.1, an internal vertex x_j is isolated in the threshold partition precisely when T_j<t; otherwise it is connected to its home terminal. Call it active in the latter case. The threshold relation induced on terminals is exactly the logical relation. These statements can equivalently be checked using raw real edges of activity at least t, since taking the bottleneck closure leaves threshold components unchanged.
Remove the neutral pairs one at a time from the current hole set. For a pair on the same side, its active vertices lie in one class. Removing it reduces S'_t by at most
Indeed, two active holes are removed from one class, one active hole reduces a class floor by at most one, and an inactive hole is in a singleton class and contributes zero. On the left \max(T_j,T_k)=T_j; on the right it is T_k. For a cross pair, the loss is at most
To see the subtracted term, when \lambda_e\ge t both vertices are active and are connected by the full path, so their removal reduces a single class floor by one. Otherwise the bound is the sum of the separate active-hole bounds. These arguments apply to the current set after any preceding removals.
Next consider each consumed hole mapping away from home. If it is active and \lambda_e<t, discard it. The floor loss is at most
The expression is nonnegative, since T_j\ge B_e\ge\lambda_e. Every remaining active consumed hole can be mapped to its consumed terminal within its threshold class: a home mapping always has this property, and an away mapping retained by the rule has \lambda_e\ge t. Together with explicitly deleted terminals, these maps are injective, by the distinctness in Remark 4.4. Inactive internal holes lie in singleton classes and contribute no floor. Hence the floor sum remaining after the removals and discards is at most S_t(R).
Integrate these bounds against dt/t on (1,\infty). By Remark 4.5, the integral of S'_t(U) is \log\Phi_{B'}(U), and that of S_t(R) is \log\Phi_B(R). For a same-side neutral pair the integrated charge is exactly -\log f_{jk}. For a cross pair it is
For an away-mapped hole it is
Home mappings cost zero. Summing proves \log\Phi_{B'}(U)\le\log\Phi_B(R)-\log F, which is Equation (4.9). Finally, Remarks 4.4 and 3.1 give
Proof of Remark 4.3. Expand the partition function before collapsing real and virtual portions. A nonempty partial matching Q of a colored virtual edges, with endpoint set U, contributes relative to Z' the mass
Vertices sharing l lie in the same threshold component at h_l, so h_l\le B'_{xy}. Their pairing therefore gives
by Remark 4.6. A vertex pair has at most two common labels, so there are fewer than N^2 colored virtual edges and at most N^{2a} choices for Q. The empty Q contributes one. Consequently,
5 A quadrangulation adapted to the labels
We now turn to the sampling branch of the proof. Its input is a tree-bag graph as in Remark 2.1; no balance assumption is needed. To compare two alternating matchings on a cycle, we shall subdivide its polygon into four-corner cells. A cell side may stand for a long arc of the original cycle. We first describe the matching patterns on such an arc and the endpoint repairs the cells must permit, then construct a quadrangulation with those properties.
Let \mathcal C be a simple even cycle of length m\ge4 in the colored bag graph. Each edge retains its color, which is a node of the label tree. For a vertex v of \mathcal C, define
Thus S_v is a singleton or consists of two adjacent tree nodes. These sets refer to the original full cycle throughout the construction; adding a diagonal never changes them. In particular, the cyclic sequence of edge labels is a walk on the tree, with repetitions allowed.
An arc is one of the two paths in \mathcal C between distinct vertices, specified together with its endpoints. Its length is its number of edges. We use only odd arcs. An arc is admissible if its endpoints u,v satisfy S_u\cap S_v\ne\varnothing. The clique property then supplies an edge joining them with any chosen label in this intersection.
For an admissible odd arc J=(v_0,\ldots,v_s), choose such a colored endpoint chord e_J and put
All path edges retain their cycle colors. The through pattern T_J and the closed pattern C_J both perfectly match the vertices of J; the interior pattern N_J leaves only its two endpoints unmatched. The symbol C_J denotes a matching, not the original cycle. Call J short if s=1 and long otherwise. On a short arc choose its actual cycle edge as e_J, so T_J=C_J. When a diagonal later represents two complementary arcs, we use the same colored chord in both patterns. Figure 2 shows these patterns on a long arc.
Figure 2: The two patterns on a long odd arc, illustrated for J=(v_0,\ldots,v_5). Solid edges form the indicated matching; faint dashed edges only locate the underlying path. Both T_J and C_J perfectly match the same vertices. The latter uses the interior pattern N_J and the endpoint chord e_J; their union T_J\cup C_J is the alternating cycle consisting of J and its chord. Replacing T_J by C_J can change interior edges; this replacement need not be a single chain update.
Besides closing an arc with a chord, we shall sometimes need to free its endpoints while starting from its through pattern. Removing the first and last edges of a long arc from T_J uncovers its endpoints and its two leaves v_1,v_{s-1}. Call J good if it is short or if
For a good long arc, choose an edge between its leaves with a label in this intersection, called a leaf repair. After the two boundary edges are removed, inserting this repair matches all internal vertices and leaves both endpoints free. For a short arc, deleting its sole edge does the same. This is the matching operation encoded by the good-arc condition. The boundary edges of an arc mean only its first and last edges, which coincide for a short arc.
Realize the vertices of \mathcal C in their cyclic order as a convex polygon. A quadrangulation is a subdivision of this polygon into quadrilaterals by noncrossing diagonals. A side of a cell represents the arc of the original cycle from one corner to the next corner, containing no other corner of that cell. Consequently the four sides of each cell represent four consecutive arcs partitioning the entire cycle. An interior diagonal has two occurrences as a cell side, and their arcs are complementary in the original cycle.
Lemma 5.1 (Label-adapted quadrangulation). The polygon of \mathcal C has a quadrangulation such that every cell side represents an admissible odd arc and the following hold in every cell:
- (i)
some opposite pair of sides consists of good arcs;
- (ii)
if both arcs in an opposite pair are long, both arcs in the other opposite pair are good.
There are (m-2)/2 cells and (m-4)/2 interior diagonals. One can construct the quadrangulation in time polynomial in m and the encoding length of the label tree.
Each diagonal may be assigned any common label from the fixed sets at its endpoints, used consistently in its two occurrences. For a short side, use the color of its actual cycle edge. These choices need not coincide with the auxiliary labels used in the construction.
Proof. We give a recursive splitting rule. A subproblem is an admissible odd arc J=(v_0,\ldots,v_s); its exterior is its complementary arc in the full cycle. Choose a label P\in S_{v_0}\cap S_{v_s}, and write a_i for the label of v_iv_{i+1}, 0\le i<s. Adjacent terms of this sequence are equal or adjacent in the tree. If s=1, no cell is needed. For s\ge3, we find indices
such that the three subarcs with successive endpoint pairs
are admissible. They and the exterior arc form the four sides of the new cell. We call these the first, middle, third, and exterior sides, respectively.
We repeatedly use the following elementary fact about a tree. If a contiguous part of the label walk avoids P and its first and last labels are adjacent to P, these two labels coincide: the walk lies in a single component of the tree with P removed, and that component has just one node adjacent to P.
The exterior is good. It suffices to make either the middle side short or both the first and third sides short. Either alternative immediately implies (i) and (ii), because the exterior is good.
First ensure that some a_i equals P. If none does, a_0 and a_{s-1} are adjacent to P, because the endpoint sets contain P. The elementary tree fact gives a_0=a_{s-1}=Q for a neighbor Q of P. Replace P by Q, which also lies in both endpoint sets. We now distinguish the exhaustive possibilities below.
- (a)
Suppose a_i=P for an odd i. Set p_1=i and p_2=i+1. The middle side is short. The first side’s two endpoints contain P, as do the third side’s two endpoints, so all three sides are admissible.
- (b)
Otherwise all occurrences of P have even indices. If their first index is i>0, set p_1=i-1 and p_2=i. The prefix a_0,\ldots,a_{i-1} avoids P, and its first and last labels are adjacent to P. They therefore equal the same neighbor Q. The first side’s endpoints both contain Q, and the third side’s endpoints both contain P. The middle side is short.
- (c)
Suppose the first occurrence is at 0, but the last occurrence is at j<s-1. Set p_1=j+1 and p_2=j+2. The suffix a_{j+1},\ldots,a_{s-1} avoids P and has its two end labels adjacent to P, so they equal one neighbor Q. The first side’s endpoints contain P, the third side’s endpoints contain Q, and the middle side is short.
- (d)
In the remaining case a_0=a_{s-1}=P. Set p_1=1 and p_2=s-1. Both outer sides are short, and the middle side’s endpoints both contain P.
All indices satisfy (5.1). For example, in (b) the even index i is at least 2, and in (c) the even index j is at most s-3.
The exterior is not good. The exterior is then long. At least one of its leaves lacks P in its fixed label set, since otherwise its two leaves would share P. Reverse the indexing of J if necessary so that this leaf is the exterior neighbor of v_0. The exterior edge at v_0 cannot have label P. Since P\in S_{v_0}, the first edge of J must have label a_0=P.
If a_{s-1}=P as well, choose p_1=1,p_2=s-1. Both outer sides are short, and the middle side is admissible. Otherwise let t-1 be the last index with a_{t-1}=P. Thus 1\le t\le s-1. The suffix a_t,\ldots,a_{s-1} avoids P. Its first label is adjacent to P, and its last label is adjacent to P because P\in S_{v_s}. Hence
for the same neighbor Q of P.
- •
If t is even, set p_1=1,p_2=t. The first side is short. The middle side’s endpoints both contain P, and the third side’s endpoints both contain Q. The third side is good: if long, both its boundary edges have label Q, so both its leaves contain Q.
- •
If t is odd, set p_1=t,p_2=s-1. The third side is short. The first side’s endpoints both contain P, and the middle side’s endpoints both contain Q. The first side is good because, if long, both its boundary edges have label P.
The required strict inequalities follow from t\ge2 in the even case and t\le s-2 in the odd case. In either case the first and third sides are good and at least one is short. This proves (i). The only opposite pair that can contain two long sides is the middle–exterior pair, and its other pair is good, proving (ii).
Recursion and consistent diagonals. Start with any arc of length m-1, whose exterior is the remaining single cycle edge. Its endpoints share that edge’s label. Apply the splitting rule and recurse on each of the three subarcs whose length exceeds one, always using the original sets S_v and the complement in the original cycle as exterior. The three subpolygons have disjoint interiors, so all diagonals are noncrossing. Each recursive child has odd length and admissible endpoints by the construction. The splitting label P is only an auxiliary witness to admissibility; it does not constrain the color of the closing diagonal. Thus each diagonal can be colored once and the same color used on both sides.
For an odd arc of length s, the resulting number of cells is (s-1)/2: this is zero for s=1, and a split into odd lengths s_1+s_2+s_3=s gives
The root therefore gives (m-2)/2 cells. Each nonroot recursive subproblem that creates a cell has one closing diagonal, giving one fewer interior diagonals than cells. A direct implementation scans at most m labels in each of the (m-2)/2 nontrivial subproblems; the recursion also has m-1 short leaf arcs. Fixing total orders for any choices makes the construction deterministic, with O(m^2) label comparisons and polynomial bit cost.
For each cell, choose its colored side chords as in Remark 5.1; for each good long side, choose one leaf repair. These are precisely the additional edges needed for the local matching constructions in the next section.
Lemma 5.2 (Comparability within a cell). Consider the four colored side chords of a cell, the first and last cycle edges of each of its four arcs, and one leaf repair for each good long arc. The labels of any two edges in this collection have tree distance at most 6. Consequently their activities lie within a factor
of one another. The same conclusion holds after clamping every edge activity to any common interval [a,b]\subset(0,\infty).
Proof. Two consecutive side chords have labels in the same fixed set S_v at their common cell corner, so their labels are equal or adjacent. Any two of the four side-chord labels therefore have distance at most 2. A boundary edge of an arc and its side chord have labels in the same S_v at the relevant endpoint, giving distance at most 1. A leaf repair and the boundary edge at either of its leaves have labels in that leaf’s fixed set, again giving distance at most 1. Thus each edge in the stated collection is at distance at most 2 from its side chord, and the diameter is at most 2+2+2=6.
Adjacent labels have heights differing by a factor 2. If edges e,f have labels \ell,\ell' with distance at most 6, the assumed activity bounds imply
The same bound holds with e,f exchanged. Finally the common clamp \psi(x)=\max\{a,\min\{b,x\}\} satisfies
For example this follows by observing that \log\psi(e^u) is the clamp of u to [\log a,\log b], a nondecreasing 1-Lipschitz function. Clamping therefore preserves the factor bound.
6 A two-coordinate energy inequality
This section proves the sampling argument’s main inequality. The four side chords of each cell give a two-edge switch whose changed edges have comparable activities. Long arc conversions are used in an exact signed identity and need not be individual chain moves. We control the resulting context errors by swapping an alternating cycle with an independent matching. Encodings by two matchings change only a bounded number of edges in their multiset union, and their preimage counts give polynomial load bounds. The variance-to-energy comparison is related to the flow method of [Sinclair(1992)], but we do not invoke a path-congestion theorem: the signed identity and its context-error estimates are established for the present pair kernel.
Fix a tree-bag graph on N\ge2 vertices, with at least one perfect matching, and let w be either its reference activities or any common clamp of them. Write \pi(M)=\wt_w(M)/Z_w and \calM for its colored perfect matchings. Throughout this section put
6.1 The pair kernel
On (A,B)\in\calM^2, choose each of the following proposal types with probability 1/3.
- (1)
Two-edge switch. Choose an unordered pair of distinct edges of A uniformly, and choose either alternative pairing of their four endpoints with probability 1/2. For each proposed edge, choose index 1 or 2 with probability 1/2 from the ordered list of common labels of its endpoints. If an index is absent, stay put. If A has fewer than two edges, stay put.
- (2)
Color change. Choose an edge of A uniformly and choose index 1 or 2 from the common-label list with probability 1/2. An absent index gives a holding move.
- (3)
Cycle swap. Choose uniformly one discrepancy cycle of A,B and interchange its two layers. If there is no discrepancy cycle, stay put.
Accept each proposal by the Metropolis rule for \pi\otimes\pi. Denote the resulting kernel by P and its energy by \calE. The proposal is symmetric. For the first two types, the reverse choice has the same edge, pairing, and color-index probabilities; the possible holding choices do not change this fact. For the third type, the discrepancy cycles and their number are unchanged by the swap. In particular, a cycle swap always has acceptance probability one, since its product weight is unchanged.
Theorem 6.1 (Pair energy inequality). For every two real functions f_1,f_2 on \calM,
The same constant works for every common-interval clamp of the reference activities.
In the proof write F(A,B)=f_1(A)+f_2(B) and E=\calE(F). A two-edge switch is called safe if its four removed or inserted colored edges have activities within a factor A_0 of one another. Let \mathcal S(A) be its possible safe destinations, and let \mathcal K(A) be its possible destinations by changing one edge color. Consecutive labels have comparable heights, so every color change has activity ratio in [A_0^{-1},A_0].
Lemma 6.2 (Elementary energy bounds). With the notation above,
Here \mathcal C(A,B) denotes the discrepancy cycles, and (A,B)^C is the pair after swapping C.
Proof. Every specified legal two-edge switch has proposal probability at least 1/(30N^2); its Metropolis acceptance is at least A_0^{-2} when safe. Every specified color change has proposal probability at least 1/(6N) and acceptance at least A_0^{-1}. These moves change only the f_1 summand of F, so summing the second-coordinate law and using the factor 1/2 in the energy proves the first two bounds. There are at most N discrepancy cycles. Each specified swap therefore has proposal probability at least 1/(3N) and is accepted; this proves the third bound.
6.2 An exact identity on a cycle
Fix a pair of demand matchings (I_1,I_2) and a simple discrepancy cycle C of length at least four. All orientations and choices below are deterministic, using the orders fixed in Section 2. Let R be the edges of I_1 outside C, and let O_0=I_1 and O_1 be the matching obtained by toggling C in I_1. Thus both orientations use R outside C. Put
Apply Remark 5.1 and fix the colors of its diagonals consistently. A cell’s four sides always mean the four odd arcs of the original whole cycle, not paths formed from earlier diagonals.
Use the through, interior, and closed patterns T_J,N_J,C_J from Section 5, with the chosen chord colors. A side J is through in O_\varepsilon if T_J\subseteq O_\varepsilon. Exactly one orientation O_\varepsilon contains T_J; define
For a short side, the chord is its actual cycle edge, so g_J=0.
The reason for using the original cycle on every cell side is already visible on a six-cycle C=(v_0,\ldots,v_5,v_0). Take
and suppose the diagonal e=v_0v_3 is admissible. In the two cells it represents the complementary arcs J=(v_3,v_4,v_5,v_0) and \bar J=(v_0,v_1,v_2,v_3), respectively. Both conversions yield the same matching
Thus g_{\bar J}-g_J=f_1(O_0)-f_1(O_1)=D_C; the shared diagonal contributes one whole-cycle difference, not zero. Figure 3 displays this common converted matching. This example isolates the complementary-gain identity. Its cells have only one long side each, so the context errors introduced below vanish; cells with two opposite long sides require a further estimate.
Figure 3: An admissible diagonal e=v_0v_3 cuts a six-cycle into two cells. In the upper cell its side follows the lower boundary arc J; in the lower cell its side follows the upper boundary arc \bar J. The two occurrences use the same colored edge e. Converting the through pattern on either arc gives the restriction of H shown on the right (the common outside matching R is omitted), so their signed gains sum to D_C. The drawing concerns the signed identity, not a sequence of chain transitions.
In a cell, let P be its opposite pair of sides through in O_0, and Q its opposite pair through in O_1. Let A_P use N_J on every side and the chords of the two sides of P, together with R. Define A_Q analogously and put
These are legal perfect matchings: the interior vertices are matched by the N_J’s, and the two chosen chords match the four corners. Their difference is a safe two-edge switch by Remark 5.2.
Order each opposite pair as (Y,X). For the orientation in which both are through, first convert Y and then X. Write A^{(0)}=O_\varepsilon and A^{(1)}=H_Y for the two pre-conversion contexts of X. For a matching R' on the vertices outside X, define
The context error of the ordered opposite pair is
It is zero if either side is short. Denote these errors by E_P,E_Q for the two ordered pairs of the cell.
Lemma 6.3 (Cell identity and cancellation). The quantities just defined satisfy
for each cell. Consequently,
Proof. The first conversion in an opposite pair has its canonical gain. The second has its canonical gain plus the error in (6.8). Thus
Subtracting proves (6.9).
Consider an interior diagonal with complementary arcs J,\bar J. They are through in opposite whole-cycle orientations, and their converted matchings coincide:
Therefore the two signed canonical gains contributed by this diagonal sum to f_1(O_0)-f_1(O_1)=D_C. The signs here are precisely those in (6.9): the arc through in O_0 has positive sign and the other negative sign. Boundary sides have zero gain. Summing (6.9) over the cells therefore gives one copy of D_C per cell on the left and one per interior diagonal on the right, in addition to the displayed local terms. The number of cells is one more than the number of diagonals, which proves (6.10).
6.3 Encoding the demands
A switch demand specifies (I_1,I_2), a simple discrepancy cycle C, and one cell of its fixed quadrangulation. Its value is \Delta above. An error demand specifies these data and one opposite pair with two long sides, in its fixed order (Y,X). Its value is E_{Y,X}. The weight of either demand is \rho(d)=\pi(I_1)\pi(I_2). Repeated demands from different cells or different cycles are included separately in all sums.
Lemma 6.4 (Encodings with a bounded number of preimages). Every switch demand has an encoding (A_P,B) by two perfect matchings, and every error demand has encodings (A^{(j)},B^{(j)}) for j=0,1, with the following properties.
- (i)
For each encoding (A,B), \rho(d)\le A_0^4\pi(A)\pi(B).
- (ii)
For each encoding type and each fixed output pair, there are at most \calT demand preimages. This bound includes the choices of cycle, cell, opposite pair, and context.
- (iii)
For an error demand, both guide matchings satisfy C_X\subseteq B^{(j)}.
Proof. We first describe a repair operation. Start with the union of the four through patterns T_J in a cell. Each corner is covered twice, once by each incident side. Select a good opposite pair of sides. For each selected short side delete its sole edge. For each selected long side delete its first and last edges, and insert its chosen leaf repair. Each corner loses exactly one incident edge. On a long selected side the only newly uncovered internal vertices are its two leaves, which the repair matches. Thus the resulting edges form a perfect matching of all cycle vertices. This verifies legality also for a side of length three: its two leaves are distinct and its repair is an ordinary colored edge between them.
Switch demands. Use A_P as the first output. In the second output retain the edges of I_2 outside C, start with all four through patterns, and apply the preceding repair operation to a good opposite pair, which exists by Remark 5.1(i). Call the result B. Before these modifications, the original multiset union contains exactly one T_J and one N_J on each side. The output union adds the two P-chords and the leaf repairs and drops the selected boundary edges. If r\in\{0,1,2\} selected sides are long, the numbers added and dropped are both 2+r\le4.
Error demands, context zero. The first output is A^{(0)}=O_\varepsilon, the canonical orientation in which X,Y are through. Start the second output with the complementary cycle orientation and the edges of I_2 outside C. It has the N patterns on X,Y. Insert their two chords. The other opposite pair is good by Remark 5.1(ii), because X,Y are both long. On that other pair delete boundary edges and insert leaf repairs as above. The result is a perfect matching B^{(0)}, containing both C_X and C_Y. Again, the multiset union differs from the original by equally many added and dropped edges, at most four of each.
Error demands, context one. Interchange the patterns T_Y and C_Y between A^{(0)},B^{(0)}. Each pattern perfectly matches the entire vertex set of Y, so the interchange is legal and gives A^{(1)}=H_Y and a guide B^{(1)}. The vertex sets of the opposite arcs X,Y are disjoint; hence B^{(1)} still contains C_X. This interchange does not change the multiset union or product weight.
In every case all added and dropped edges are among the chords, boundary edges, and good-side leaf repairs of this one cell. They have pairwise activity ratio at most A_0 by Remark 5.2. Since the two lists have equal length at most four, the input product weight is at most A_0^4 times the output product weight. Division by Z_w^2 proves (i).
For completeness we give an inverse, including the information it needs. Attach a tag consisting of the four cell corners in cyclic order, lists of the added and dropped colored edges padded to length four each, one orientation bit, and fixed flags for the encoding type (switch, error context zero, or error context one), opposite pair, and order. An edge in these lists is an occurrence in the multiset union; coincident colored edges retain their multiplicities. Given the output pair and tag, remove the added occurrences and reinsert the dropped occurrences in its multiset union. This recovers the original colored union I_1\uplus I_2. Its component containing the first tagged corner is the active simple cycle C. The orientation bit specifies which of the two alternating classes at that corner belongs to I_1, so alternation determines both original layers on all of C. Outside C, the output layers were unchanged; they recover I_1,I_2 there directly. The fixed quadrangulation can now be reconstructed. Its tagged corners identify the cell, and the flags identify the term and, if appropriate, its ordered pair. Thus this is an inverse on every tag produced by the construction.
There are at most 2N^2 possible colored edges. Allowing a padding symbol, the tags have at most
possibilities for N\ge2. Here the factor 128 more than covers the orientation bit and the fixed flags; the lists themselves may be stored in the fixed colored-edge order. This proves (ii), and the constructions already proved (iii).
The encodings provide two kinds of control. Their bounded preimage count converts a sum over demands to a sum over pairs of matchings. For context errors, the guide also contains a prescribed closed arc; this additional condition must survive that summation. We use the bounded preimage count for switches below, then retain the closed-arc condition when treating context errors in the next subsection.
We apply this lemma first to switches. For a fixed encoded pair (A,B) there are at most \calT demands, and each has its associated destination A_Q in \mathcal S(A). Therefore
6.4 Controlling context errors by cycle swaps
Here an identity X means a directed, colored, simple odd path of length at least three together with a specified colored edge joining its endpoints. It determines T_X,C_X and (6.7). We may sum over all such identities: this is a finite proof device, and the algorithm does not enumerate them. Put
We omit identities with p_X=0. Every identity arising from an error demand has p_X>0, by the guide constructed in Remark 6.4. For any first matching A\supseteq T_X and either j=0,1, that lemma gives the following conditional demand-mass bound:
Indeed, for each guide B\supseteq C_X there are at most \calT preimages of (A,B); now sum its product weight over these guides. The factor p_X is essential and will cancel the conditioning below.
The next comparison averages over precisely those guides counted by p_X. That conditional law can be concentrated on a very rare event. We therefore retain p_X in the demand bound instead of estimating it from below.
For a fresh guide B\sim\pi, define
For an error demand, (6.8) and (a-b)^2\le2(a-c)^2+2(b-c)^2 imply
Applying (6.12), and then Jensen’s inequality to the conditional expectation defining \mu_X, gives
where
In detail, for a fixed X,A Jensen bounds the squared difference from \mu_X by
Multiplication by the p_X in (6.12) removes this denominator exactly. No lower bound on p_X is used.
Lemma 6.5 (Swap sum). The sum in (6.14) satisfies \Sigma_{\rm swap}\le12N^2E.
Proof. For a pair in (6.14), the matchings T_X and C_X cover exactly the same vertex set, and their union is one alternating cycle: the path X together with its closing chord. Their edges are disjoint since X is long and simple. Thus this is an entire discrepancy component of A,B, not a portion of a larger one. Swapping it changes F by exactly
For a fixed fresh pair (A,B) and one of its discrepancy cycles, an identity X is determined by marking the closing chord in the second matching and choosing a direction around that cycle. The remaining colored path is then read from the pair. There are at most 2N such choices. Consequently
by (6.5).
6.5 Completion of the energy proof
Proof of Remark 6.1. Take independent I_1,I_2 with law \pi. Toggle their discrepancy cycles in the order of their least vertices, converting I_1 to I_2. Cauchy–Schwarz over the at most N cycles gives
For each selected C, toggle all earlier cycles in both demand matchings. This preserves their product weight, their union, and the selected cycle. It is its own inverse, since the union fixes the same cycle order. The term at that step becomes D_C^2 for the new demand pair, with the definition used above. Since \Var_\pi f_1=\tfrac12\E(f_1(I_1)-f_1(I_2))^2, we obtain the convenient slightly weaker bound
A length-two discrepancy cycle is a color change in I_1. For a fixed I_1 and specified change, summing the mass of I_2 that supplies the other color costs at most one. Its total contribution to the sum in (6.15) is therefore at most 12NA_0E, by (6.4).
For a simple cycle, there are fewer than N cells, so (6.10) and Cauchy–Schwarz give
Sum over all such cycle demands. The errors with a short side vanish; all others are precisely the error demands already bounded. Equations (6.11), (6.13), and Remark 6.5 bound the simple-cycle contribution by
Combining the two cycle types in (6.15) and using A_0,\calT\ge1 yields
Finally
All comparisons used only Remark 5.2 and the adjacent-label comparison for color changes. Both hold under any common clamp, proving the final assertion as well.
7 A sampler from replicated adjacent tiers
The two-coordinate inequality controls an additive function of a pair; it is not a Poincaré inequality for all functions of that pair. We now turn it into a Poincaré inequality on a larger product space. The construction uses adjacent weight tiers, with many independent copies at each tier. Orthogonality of product projections controls the terms involving both members of a pair. The slot order ensures that no orthogonal interaction component occurs in two different pair residuals. Averaging over many guides then makes their total contribution small enough to absorb. Using several adjacent distributions in one product chain has antecedents in replica Monte Carlo [Swendsen and Wang(1986), Wang and Swendsen(2005)]. Here the coordinates are colored perfect matchings, the pair moves exchange alternating cycles, and the effect of replication is quantified by the proof below.
Throughout this section, the tree-bag graph has N\ge2 vertices, b_{\rm tree} labels, maximum level at most 2K, and the integer parameter D of Remark 2.1, where K is a nonnegative integer. Its reference activities are positive rationals. Let \calM denote its common, nonempty set of colored perfect matchings. By Equation (2.3),
7.1 An exact refresh at unit activities
Lemma 7.1. The unit-activity partition function is computable by a dynamic program on the label tree. With exact rational categorical choices, its tables also produce an exact sample. The tables can be computed with O((b_{\rm tree}+1)(N+1)^3) arithmetic operations on counts of O(N\log(N+1)) bits. Label and loop indices use O(\log(b_{\rm tree}+1)+\log(N+1)) additional bits. Once the tables are available, a sample uses polynomially many integer operations and at most 4(b_{\rm tree}+N+1) rational categorical choices, each with at most N+1 outcomes. A positive table also yields a matching by entirely deterministic backtracking.
Proof. A colored matching assigns each vertex to the color of its matched edge. Conversely, assign each vertex to one of its one or two bags, and pair the vertices assigned to each bag. These two operations are inverse. Thus, if a_l vertices are assigned to bag l, the number of matchings for that assignment is \prod_l J(a_l), where
The values of J count pairings of a complete graph.
For a nonroot bag C, write S_C for its interface with its parent, and put s_C=|S_C|; for the root use S_C=\varnothing. Let u_C be the number of vertices belonging to C alone. All interfaces incident to a bag are disjoint. For a fixed subset of k vertices of S_C assigned to C, let F_C(k) count the assignments and pairings within the subtree of C; the other vertices of S_C are assigned to its parent. The answer depends only on k: vertices of S_C belong to no bag other than C and its parent, and they are interchangeable in the complete clique of color C.
If C_1,\ldots,C_d are the children of C, set s_i=s_{C_i}. Choosing \ell_i vertices of the ith interface to be assigned downward gives the recurrence
The required partition function is F_{\rm root}(0). There is no exponential enumeration in evaluating this recurrence. Form the polynomial
Its degree is at most N, and
with impossible indices contributing zero. Naive convolutions suffice for the asserted arithmetic bound. The intermediate counts enumerate assignments and partial pairings on at most N vertices. There are at most 2^N assignments, and for any one assignment at most N! such pairings, so 2^N N! bounds these counts. This gives the bit bound.
For sampling, begin at the root with k=0. At a visited bag, choose a with probability proportional to [z^a]H_C(z)J(u_C+k+a). Backtrack the stored convolutions to choose the individual \ell_i, then choose uniformly the corresponding interface subsets. Recurse on each child with its chosen subset, and independently choose a uniform pairing of the vertices assigned to the current bag. Every choice is proportional to its number of completions in Equation (7.2); induction on the subtree therefore gives the uniform law on colored matchings. A uniform subset is generated by sequential inclusion choices, and a uniform pairing by repeatedly pairing the least remaining vertex with a uniformly chosen other vertex. The total number of interface vertices is at most N, since a shared vertex belongs to exactly one interface. There are at most N/2 partner choices, b_{\rm tree} total-size choices, and b_{\rm tree}-1 convolution choices. This proves the stated draw bound. Choosing any positive-count branch instead yields a deterministic matching.
7.2 The product chain
Set
where L=(10^4ND)^{100} is the integer in Remark 6.1. At tier t\in\{0,\ldots,T\}, clamp every reference activity to [c^{-t},c^t] and denote the matching law by \pi_t. Thus \pi_0 is the uniform colored matching law and \pi_T is the desired law. Moreover,
Indeed, an individual activity changes by a factor in [c^{-1},c], so unnormalized matching weights and partition functions each change by factors in [c^{-N/2},c^{N/2}]. The probability ratio is therefore in [c^{-N},c^N], and c^N\le\exp(1/N)<2. Also \log(1+N^{-2})\ge(2N^2)^{-1}, whence
Here and below, unbased logarithms are natural.
Use q slots at each tier, with product stationary law
An allowed pair (x,y) consists of a slot x at tier t\ge1 and any slot y at tier t-1. On this pair use exactly the symmetric proposal of Remark 6.1, with local proposals acting on x, and accept by Metropolis for \pi_t\otimes\pi_{t-1}. Across unequal tiers a cycle swap uses this Metropolis acceptance ratio as well; the acceptance-one observation for two identical laws in Section 6 no longer applies. For each base slot there is instead the update that refreshes it from \pi_0, using Remark 7.1. There are
updates. The chain P holds with probability 1/2; otherwise it chooses one of these M updates uniformly. Every update preserves \nu and is reversible, so the same is true of P.
Write \calE_{xy} for the energy of one allowed pair update, with all other coordinates integrated against \nu, and \calE_i for the energy of a refresh of base slot i. In this notation
For later use, the two-coordinate inequality also applies across adjacent tiers. The pair state space and symmetric proposal are identical for the targets \pi_t\otimes\pi_t and \pi_t\otimes\pi_{t-1}. By Equation (7.4), the latter target density is at least half the former at every pair state. The Metropolis capacity formula Equation (2.5) thus shows that the unequal-tier energy dominates half the equal-tier energy. Consequently, for any functions a and b of the two slots,
In this display the energy is on the two slots alone; it can also be applied conditionally on any fixed values of other slots.
Lemma 7.2. The lazy product chain has spectral gap at least 3/(8M), and hence at least 1/(20LM). The dependence on L in the stronger bound is carried by q=32L, and hence by M.
Proof. Order the slots from highest tier to lowest, resolving ties arbitrarily. Thus every allowed guide y follows its upper slot x. For each slot x, let U_x be the set of its predecessors and put
These are the orthogonal martingale increments, so
Fix an allowed pair (x,y), abbreviate U=U_x, and define
For fixed U, h_x is centered over x and k_{xy} over y. Applying Equation (7.8) and then averaging over U gives
Conditional expectation onto U,x,y decreases \calE_{xy}: the pair kernel is independent of all the other coordinates, and Jensen’s inequality applies to each difference across a transition. For any stationary Markov kernel, Equation (2.4) and (a-b)^2\le2a^2+2b^2 give \calE(v)\le2\|v\|_2^2. Using Equation (7.10), and observing that functions of U have zero pair energy, we conclude that
We now have an estimate for one upper slot and one guide, but it contains a residual involving both slots. Replication helps only if these residual terms can be charged collectively. The ordering of slots makes that collective estimate possible.
The key point is that the residuals in this bound are orthogonal over all allowed pairs. To verify it explicitly, use the orthogonal product (ANOVA) decomposition of Efron and Stein [Efron and Stein(1981), Section 2], written here as
where S ranges over subsets of the slot set. Each f_S depends only on the coordinates in S and is centered in each coordinate of S. Therefore distinct f_S are orthogonal, and \E[f\mid A]=\sum_{S\subseteq A}f_S. Substitution into Equation (7.10) gives
Every set S in this sum has y last and x penultimate in the fixed slot order: all its other coordinates lie in U_x. These two positions determine the allowed pair uniquely. Thus even pairs that share a slot use disjoint sets of orthogonal components. Since every component here is nonconstant,
This decomposition is only an identity in the proof; the algorithm does not compute it.
For a base slot i, conditional expectation onto U_i,i similarly decreases its refresh energy. The refresh energy of h_i equals \|h_i\|_2^2, because h_i is centered over i given U_i. Hence \|h_i\|_2^2\le\calE_i(f). Average Equation (7.11) over the q guides of each nonbase slot and sum over slots. Equations (7.9) and (7.13) yield
Since q=32L, absorption gives
This proves the first gap bound. The second follows from L\ge1.
7.3 A quantitative sampling guarantee
Theorem 7.3. Define T,q,M by Equations (7.3) and (7.6), and put
Initialize all slots to any one colored perfect matching and run the exact chain for s(\xi) steps. The resulting product law is at total variation distance at most \xi from \nu. In particular, any top-tier slot has law within \xi of the desired weighted matching law.
All tables, state representations, and transition probabilities are computable by rational arithmetic. Their sizes, arithmetic operation counts, and rational bit lengths are polynomial in N,D,K, b_{\rm tree}, \log(1/\xi), and the bit lengths of the reference activities. Exact rational choices here define an ideal process; the bounded-bit implementation in Section 9 adds at most \xi to the total variation error.
Proof. Every colored matching consists of N/2 vertex pairs, each with at most two color choices. In particular, |\calM|\le(2N^2)^N. At every tier, all activities remain in the interval Equation (7.1). For any A\in\calM this gives
Taking the product over q(T+1) slots and using N\ge2,D\ge1 shows that
For example, with a=\lceil\log_2(ND+2)\rceil, the logarithm of the denominator in the preceding display is at most N(K+\tfrac52a+2), which is at most 10N(K+a+1).
For completeness, the finite-state spectral argument gives a direct mixing bound. Reversibility makes P self-adjoint on L^2(\nu). Its laziness makes its eigenvalues nonnegative, and Remark 7.2 bounds every eigenvalue on the centered subspace above by 1-\gamma, where \gamma=1/(20LM). Starting from a point z, the centered initial density has squared norm 1/\nu(z)-1. By diagonalization, reversibility, and Equation (7.16),
Substitution of Equation (7.15) makes this at most \xi. Projection onto a chosen top-tier coordinate cannot increase total variation.
It remains to specify the computation represented by this chain. The unit-activity tables are supplied by Remark 7.1; a positive table supplies an initial matching if one has not already been constructed. There are at most N^2 colored edges and q(T+1) matching coordinates. Precompute the clamped activities at every tier using rational powers of c. The tier bound Equation (7.5) is polynomial in the stated parameters, and these powers have polynomial bit length. A scan choice can be made by an integer in \{1,\ldots,M\}, decoding either a base slot or an upper tier and two slot indices. A pair proposal is implemented by inspecting two matchings: the alternating components can be listed by following the union of their edges, and the local switch and color proposals require only finite lists of edges and at most two color choices per new edge. Metropolis acceptance uses a ratio of products of at most 2N activities; the unknown partition functions cancel. A refresh uses the precomputed integer tables. Thus a step has polynomial arithmetic cost and rational probabilities of polynomial bit length. The bound s(\xi) is itself polynomial in the displayed parameters, which proves the assertion about the ideal computation.
For the finite-bit assertion in this generality, including arbitrarily many empty bags, use the draw and option bounds
Indeed a refresh uses at most 4(b_{\rm tree}+N+1) categorical choices, and laziness and the scan use two more. A pair step uses at most eight choices. A final revelation of edge types, when present, uses at most N further choices. These fit the displayed draw bound. Every choice has at most R_{\rm opt} options. Take a fixed integer k with 2^k\ge2R_{\rm draw}^{\rm gen}R_{\rm opt}/\xi. Remark 9.1 and successive coupling then bound the cumulative simulation discrepancy by \xi. This precision and the resulting bit cost are polynomial in the stated parameters, including b_{\rm tree}. For the hierarchy constructed in Section 4, the smaller specialized bookkeeping in Section 9 follows from b_{\rm tree}\le N(2K+1).
8 From samples to the number of perfect matchings
We now give the counting algorithm. Its sampling calls use only the tree-bag sampler proved above. In particular, neither balancing nor estimating a partition ratio requires an additional oracle. Positive completion, gradual suppression of nonedges, and estimation of successive partition ratios follow the annealing framework used for the permanent [Jerrum et al.(2004)Jerrum, Sinclair, and Vigoda]. The marked observables and vertex-scale update below supply the general-graph implementation and its balance guarantees.
8.1 The schedule and vertex scales
If n=|V|=0, return one. If a binary vertex count is used and n>2|E|, return zero: the listed edges cannot cover all vertices. On the remaining nonempty input, perform a deterministic perfect-matching existence test and return zero if it fails. Thus the remaining case has even n\ge2 and Z(G)\ge1. Set
Since \log(1+1/n)\ge1/(2n),
At stage j\in\{0,\ldots,K\} the complete logical graph has raw activities
Write Z_j for its perfect-matching partition function. Then
For sampling, we additionally maintain positive vertex scales s_i and use activities \lambda_{ij}=w^{(j)}_{ij}s_i s_j. Every perfect matching has the same vertex factor \prod_i s_i. Consequently
Initialize s_i=1/\floor{\sqrt{n-1}}. At stage zero,
so the logical graph is balanced. The update defined below always multiplies each scale by a positive number at most two, whether or not the estimates succeed. Starting from scales at most one and making at most K updates, we therefore have at every sampling call
We use the same structural parameters throughout a trial:
For each current \lambda, construct the enlarged graph and marked bag edges of Section 4.
8.2 Observables from one marked sample
Let \lambda^+ denote the activities at the next raw stage, with the current vertex scales retained. If P is a logical perfect matching, or a logical matching missing one specified pair of vertices, put
Thus \wt_{\lambda^+}(P)=u(P)\wt_\lambda(P) and
The strict left inequality follows from (1+1/n)^{n/2}<\mathrm e^{1/2}<2.
Sample a colored perfect matching from the bag graph and reveal the real, virtual, and probe portions of its edges. Define the following observables, all in [0,1]:
Here P is decoded only on the indicated event; elsewhere the observable is zero. On the all-real event it is a full logical perfect matching. On the sole-probe event it is a logical perfect matching missing i,j. Write I=Z_{\rm bag}/Z' for the inflation factor. Under the exact marked bag law, the means satisfy
The all-real probability in Remark 4.2 gives the first equality. The other two follow by multiplying the weights in that event, or in the sole-probe identity (4.4), by u(P) and summing. In particular,
Thus one batch of marked samples will estimate both the next raw partition ratio and the two-hole ratios needed to choose the next vertex scales.
8.3 Estimating and restoring balance
Use
At each stage make S independent fresh sampler runs, each with marked output law at total variation distance at most 3\xi from the exact marked bag law. Section 9 implements these runs in bounded bit time. Let bars denote the empirical means of the observables. Set
If \bar d>0, form the symmetric array
If \bar d=0, set all G_{ij}=1. The following elementary balancing procedure will be useful.
Lemma 8.1. Suppose G is symmetric and \alpha\le G_{ij}\le3 for i\ne j. Initialize v_i=2 for every vertex and visit the vertices in their fixed order, setting
Every coordinate only decreases, all final coordinates lie in [\alpha/2,2], and the final vector satisfies v_i v_j\ge G_{ij} with an equality in every row.
Proof. Initially all products equal four and hence dominate G. At an update, feasibility shows that the new value is at most the old value. The definition restores all constraints involving i and leaves all other constraints unchanged. Since every other coordinate is at most two, the new value is at least \alpha/2. At least one constraint involving i is tight. If its neighbor is visited later, that neighbor cannot decrease without violating this tight constraint. Thus the equality persists to the end.
After estimating the current ratio, perform this procedure and replace s_i by s_i v_i. These scales are used with the next raw stage.
Algorithm outline. After the zero test, one trial uses the parameters in Equations (8.1), (8.6) and (8.10) and the initial scales above. For j=0,\ldots,K-1:
- 1.
Form \lambda_{uv}=w^{(j)}_{uv}s_us_v and its marked bag graph.
- 2.
Obtain S independent fresh marked samples using the bounded-bit implementation of Remark 7.3. Compute the empirical means, then \widehat R_j and G by Equations (8.11) and (8.12), including their zero-denominator conventions.
- 3.
Run the one-pass update (8.13) on G, replace s_i by s_iv_i, and advance to the next raw stage.
The trial returns Y=(n-1)!!\prod_{j=0}^{K-1}\widehat R_j; the final algorithm takes the median of independent trials as specified below. The current scales are held fixed during each ratio estimate, so their common factors cancel. Every empirical history executes these same steps with the unconditional caps above. Balance is used only to prove the accuracy of histories whose estimates succeed.
Lemma 8.2. Suppose the current logical activities are balanced and every empirical mean is within \sigma of its exact mean. Then the next scaled activities are balanced and
Proof. By Remark 4.3 and (8.7),
Reweighting both a full matching and a matching with two holes by factors in [1/2,1] gives
In particular the pre-update row maxima lie in [1/8,2]. Write g^+_{ij}=g_{\lambda^+}(ij). Since \bar d\ge\E d-\sigma>0,
The last inequality follows from D\ge1 and \sigma\le\alpha/(100D). Since 0\le g^+_{ij}\le2, both truncations in (8.12) preserve
During the scaling procedure every updated coordinate satisfies v_i\ge\max_jG_{ij}/2\ge1/16. At the end all entries of the newly scaled two-hole matrix are at most one, by feasibility and (8.4). In each row choose a final tight neighbor. For that pair,
This proves balance.
For the ratio estimate, using R\ge1/2 and \bar a\ge1/2-\sigma,
8.4 Success probability and output
The form of Hoeffding’s inequality [Hoeffding(1963), Theorem 2] used here is: if X_1,\ldots,X_S are independent, take values in [0,1], and have a common mean \mu, then, for every t>0,
The theorem applies separately to each observable; the observables within a single sample need not be independent.
Condition on any history in which all preceding stages succeeded. By Remark 8.2, the current activities are balanced. For independent ideal samples, a union bound over the at most n^2+2 observables gives failure probability at most
One elementary verification of the last strict inequality is \log(200K(n^2+2))\le6+K+2n<20(n+K+1) for n\ge2,K\ge1. The actual fresh runs can be coupled to these ideal samples with disagreement probability at most 3S\xi=3/(1000K). Therefore the conditional probability of failure at the first unsuccessful stage is at most 13/(1000K). Summing over all K stages proves that a whole trial succeeds with probability at least 1-13/1000>0.9.
The trial output is the nonnegative rational
On success, Remark 8.2 and \prod_i(1-t_i)\ge1-\sum_i t_i for t_i\in[0,1] imply
Every matching using a nonedge has raw final weight at most b^{-K}. There are at most (n-1)!!\le n^{n/2} perfect matchings on the complete graph, so
For 0<\eps<1, the resulting lower bound exceeds (1-\eps)Z(G), and the upper bound is at most (1+\eps)Z(G). For example, \exp(\eps/100)\le1+\eps/50, which gives
To amplify, let \ell=\ceil{\log_2(1/\delta)}, computed by rational comparisons with powers of two. Run r=10(\ell+1)+1 independent trials and return their median. This is an odd number of trials. Since each succeeds with probability at least 0.9, Hoeffding’s inequality for their success indicators bounds the probability of fewer than half succeeding by
Whenever a majority succeed, the median belongs to the desired interval. The deterministic zero branch was taken before any trials. This proves the correctness and probability assertions of Remark 1.1, subject only to the bit implementation established next.
9 A bounded-bit implementation
We finish by specifying a classical finite-bit implementation and proving a worst-case bound. The argument is uniform over all empirical histories, including histories on which balance is lost. Balance controls the statistical accuracy of a successful trial; the unconditional caps in the algorithm control its running time.
9.1 Sizes of the parameters and state spaces
Let \mathsf b be the total binary input length. We use a standard explicit encoding of a finite graph and of the two rationals. If isolated vertices are specified by a binary vertex count, first return zero when n>2|E|. This test is valid for every nonempty graph admitting a perfect matching and ensures that the nonzero branch has n\le2|E|=O(\mathsf b). The deterministic existence test [Edmonds(1965)] therefore has polynomial bit cost on the original graph. It is the only matching-existence oracle used.
Equation (8.2) bounds K polynomially in \mathsf b. It can be found without logarithms by iterating rational powers of b and comparing the two sides of (8.1). The parameters p,N,D_0,D are integers of polynomial numerical size in n,K. The hierarchy has at most
nodes, since its levels are 0,\ldots,2K and every level has at most N components. The number of colored edges is less than N^2.
Use the ladder parameters c,T,L,q,M,\Lambda from Equations (6.1), (7.3), (7.6) and (7.14), and write
where s(\xi) is defined in (7.15). The structural parameters N,D,K are fixed throughout a trial. Hence the same T makes the final tier unclamped on every empirical history, by Equations (8.5) and (7.1). It can be found by iterating rational powers of c until the defining inequality in (7.3) holds. The bound (7.5) is polynomial in N,K,D. Ceilings of binary logarithms are found by integer or rational comparisons with powers of two. These bounds and the product-state size q(T+1) are polynomial in \mathsf b and \eps^{-1}. Indeed,
for an absolute constant C. The exponent 100 in L is fixed.
There is no initial-sampling problem at the upper tiers. Pair the logical vertices in their fixed order and expand this matching by the path tilings. All logical activities are positive, so this is an available real perfect matching with assigned colors. Initialize every slot to that matching. The mixing bound applies from this deterministic product state.
9.2 Rational bit lengths
We record explicitly why the adaptive scales do not create an arithmetic blowup. Put
Absolute multiplicative constants in the bit bounds below are independent of the input.
Every nonzero sample contribution is (n/(n+1))^a for some 0\le a\le n/2. These fractions have the common denominator Q=(n+1)^{n/2}. Thus empirical means, their ratios, and the capped entries G_{ij} have O(B_G) numerator and denominator bits. This bound does not involve the current scales.
An assignment in (8.13) chooses one maximizer j and sets v_i=G_{ij}/v_j. At that moment v_j is either the initial value two or an expression formed at an earlier update. Following such dependencies strictly decreases the update index, so it produces a chain of at most n factors. Each v_i consequently has O(nB_G) bits. Accumulating at most K scale updates gives O(KnB_G) bits per scale. The raw activities have O(K\log(n+1)) bits. These estimates apply even when all observations are unfavorable, because the clipping and branch conventions are unconditional.
Bottleneck entries B_{ij} and the maxima H_i=\max_{j\ne i}B_{ij} select from finitely many input activities and one; they do not involve sums over paths. Initialize B_{ij}=\max\{1,\lambda_{ij}\} and, for each vertex k, update the entries with distinct i,j\ne k by
This is the max–min Floyd–Warshall recurrence: after processing k, the entries allow the processed vertices as internal path vertices. It uses O(n^3) rational comparisons. The path profiles add only powers of two of bit length O(K). Bag activities are sums of a real activity and a dyadic height divided by D. Finally c^{\pm t} has O(T\log(N+1)) bits for t\le T.
It follows that every single-edge activity used by the sampler has numerator and denominator lengths at most the integer bound
where C_1 is a sufficiently large absolute positive integer. A product of at most N such activities has O(NB_W) bits. In a Metropolis acceptance ratio the unknown normalizing constants cancel. Thus even a cycle exchange at unequal tiers requires only rational products of this size. The real and probe revelation probabilities are likewise rational, respectively the real portion divided by the collapsed activity and 1/(DW) for the probe portion.
By Remark 7.1, the bottom-tier dynamic program uses counts of O(N\log(N+1)) bits. Its categorical normalizers count the same partial completions and obey the same bound. Label and loop indices use an additional O(\log(H_{\rm tree}+1)+\log(N+1)) bits, since b_{\rm tree}\le H_{\rm tree} in the constructed hierarchy. The table computation and sampling therefore use polynomially many integer operations with polynomial bit lengths.
9.3 Random choices with a fixed number of bits
Lemma 9.1. Let p_1,\ldots,p_r be nonnegative rational numbers summing to one. Choose a uniform integer J\in\{0,\ldots,2^k-1\} using exactly k fair bits, and return the least index i such that J/2^k<\sum_{j\le i}p_j. The output law is at total variation distance at most 2r\,2^{-k} from (p_i)_{i=1}^r.
Proof. For any interval [a,b)\subseteq[0,1), the number of grid points j/2^k in the interval differs from 2^k(b-a) by at most two. Apply this to the successive cumulative-probability intervals and sum the absolute probability discrepancies. The factor one half in total variation only improves the stated bound. An outcome with p_i=0 has an empty interval and is never returned.
The exact categorical choices in the unit-tier dynamic program define an ideal transition law. The actual algorithm implements each such choice, along with every proposal and acceptance choice, by the fixed grid in Remark 9.1. Hence exactness of the dynamic program is a counting identity; sampling from its tables in bounded bit time incurs the error budget derived below.
Every choice in the chain is either uniform on an explicitly indexed finite set, Bernoulli, or proportional to a list of nonnegative integers supplied by the dynamic program. For each used edge, final revelation is a rational categorical choice with at most three outcomes. Subsets and pairings are sampled sequentially, so no exponential list is needed. Uniform choices among the M scan positions can be implemented by integer arithmetic on the index rather than by enumerating the scan positions.
A bound on the number of random choices in one complete sampler run, including marking its output, is
To see this, laziness and the scan take two choices per step, and a pair update takes at most eight further choices. By Remark 7.1, a refresh takes at most 4(H_{\rm tree}+N+1) choices. Allowing both bounds at every step and adding the at most N choices for final marking gives
Since H_{\rm tree}=N(2K+1), this is bounded by (9.4). The bound therefore includes every categorical choice made by the implemented sampler. The number of options in any one choice is at most
Choose the same bit budget k for all these choices, with
This integer is found by doubling; k is polynomially bounded. By Remark 9.1, the sum of all conditional simulation errors is at most \xi. Successive coupling, while the simulated and exact histories agree, bounds the total variation error of the whole run and its marking by \xi. The exact-kernel mixing error is at most \xi, so the implemented marked sample is within 2\xi, and in particular 3\xi, of the required law. The number of fair bits used has a deterministic bound kR_{\rm draw}. There is no rejection loop or random convergence test.
9.4 Total bit cost
The preceding bounds already give a polynomial-time implementation. To make the accounting explicit, take a common bit bound
with a sufficiently large absolute constant C and B_W from (9.3). In particular NB_W dominates KB_G, the bit cost of multiplying the K empirical ratios. The bound B_* covers all integers used in weight products, dynamic-program counts, cumulative choices, acceptance comparisons, and output products. All categorical laws just described admit common-denominator integer weights, so computing their cumulative sums respects the same bound. Schoolbook arithmetic and the Euclidean algorithm perform the needed operations within O(B_*^3) bit time per operation.
A deliberately loose bound of O((H_{\rm tree}+1)(N+1)^4) arithmetic operations covers graph construction, the bottom-tier tables, and any one transition or refresh; storing the product state additionally takes O(q(T+1)N B_*) bits. Thus a trial, including all K stages and S fresh runs at each stage, has bit cost bounded by a fixed polynomial in
For example, the sum of
is a valid coarse envelope for arithmetic, repeated initialization, and storage operations. Each displayed parameter is polynomial in \mathsf b and \eps^{-1}. The r=10(\ceil{\log_2(1/\delta)}+1)+1 repetitions and the rational comparisons used to select their median add a factor polynomial in \log\delta^{-1} and the input length.
All data structures, loop bounds, and rational comparisons have now been specified by finite procedures. Every auxiliary parameter is bounded by a polynomial of fixed degree, and the bound holds on every random history. Together with Section 8, this completes the proof of Remark 1.1.
10 Prescribed-degree subgraphs and fixed-cardinality matchings
We record two counting consequences of Remark 1.1 and a corresponding output-sampling guarantee. Throughout this section, the input host G=(V,E) is a finite simple undirected unweighted graph whose vertices and edges are explicitly listed, including any isolated vertices. Only edges in E may be selected, so absent edges may be forbidden arbitrarily. The objects counted are labeled edge subsets, not isomorphism classes. For binary-encoded integer demands f=(f_v)_{v\in V} and a binary-encoded integer k, define
Corollary 10.1. For either family \mathcal A=\mathcal F(G,f) or \mathcal A=\mathcal M_k(G), there are uniform classical randomized algorithms with the following guarantees.
- (i)
Given rational 0<\eps<1 and 0<\delta<1/2, the counting algorithm returns a nonnegative rational \widehat N such that
\Prb[(1-\eps)|\mathcal A|\le \widehat N\le(1+\eps)|\mathcal A|] \ge1-\delta.If \mathcal A is empty, it returns zero with certainty. Its bit running time on every execution is polynomial in the full input encoding length, \eps^{-1}, and \log\delta^{-1}.
- (ii)
Given rational 0<\tau<1, the sampling algorithm reports infeasibility exactly when \mathcal A is empty. Otherwise it returns a member X of \mathcal A on every execution, and
\TV(\mathcal L(X),U_{\mathcal A})\le\tau,where U_{\mathcal A} is the uniform law on \mathcal A and \TV(\mu,\nu)=\frac12\sum_x|\mu(x)-\nu(x)|. Its bit running time on every execution is polynomial in the full input encoding length and \tau^{-1}.
Only the stated total-variation and polynomial-in-\tau^{-1} sampling guarantee is asserted. In particular, the statement does not assert exact or pointwise almost-uniform sampling. The explicit simple unweighted host model does not encode edge weights or compressed multiplicities.
10.1 Constant-fibre reductions
Write n=|V|, m=|E|, and d_v=\deg_G(v).
The prescribed-degree reduction. We use Tutte’s reduction of prescribed degrees to perfect matchings [Tutte(1954), pp. 348–349], keeping the dummy vertices labeled so that its counting multiplicity is explicit. If some f_v is outside 0\le f_v\le d_v, the family is empty and we return zero or report infeasibility, as appropriate. For valid demands put s_v=d_v-f_v. Construct a simple unweighted graph H_f with one tagged port (v,e) for every incidence of an edge e at v. For each original edge e=\{u,v\}, join (u,e) to (v,e) by a cross edge. At each v, add s_v labeled private dummy vertices, each adjacent to all d_v ports at v. There are no other edges. The tags distinguish ports and dummies, so simplicity of G makes H_f simple. Its sizes satisfy
Thus the gadget is explicit and polynomial in the host size; the initial demand check prevents expansion of arbitrarily large binary demands.
Project a perfect matching of H_f to the original edges whose cross edges it contains. Each dummy at v uses a distinct v-port. The remaining f_v ports must use cross edges, so the projection lies in \mathcal F(G,f). Conversely, an f-factor fixes its cross edges. Its remaining s_v ports at v can be bijected to the labeled dummies in s_v! ways, independently at each vertex. Hence every factor has the same number of preimages, and
The fibre may be factorial, but \log C_f=O(m\log(n+1)), so C_f has polynomial bit length. For an edgeless host with all demands zero, both the unique factor and the gadget’s unique perfect matching are empty, and C_f=1 by 0!=1. Other infeasible valid inputs give gadgets without perfect matchings by the same correspondence.
The fixed-cardinality reduction. If k<0 or 2k>n, the family is empty, so return zero or report infeasibility, as appropriate. Otherwise put q=n-2k. Form H_k by adding q labeled dummy vertices to G, joining each dummy to every original vertex, and adding no edges between dummies. Keep all original edges. This is a simple unweighted graph with at most 2n vertices and m+n^2 edges. In every perfect matching, the dummies use q distinct original vertices; the remaining 2k original vertices are paired by exactly k host edges. Conversely, a k-matching leaves q original vertices, which can be bijected to the dummies in q! ways. Therefore
Here \log C_k=O(n\log(n+1)). The same bijection covers k=0, 2k=n, and n=k=0, using 0!=1.
Proof of Remark 10.1(i). Apply Remark 1.1 to the appropriate gadget and divide its nonnegative rational output by the corresponding positive integer C_f or C_k. Compute these factorial products exactly and perform exact rational division, without rounding to an integer. Their displayed bit lengths and the polynomial gadget sizes preserve the asserted relative error, confidence, certain-zero behavior, and every-execution bit bound. This proves the counting assertion. The correspondences also make feasibility equivalent to perfect-matching feasibility in the gadget.
10.2 A deletion sampler for perfect matchings
The conversion from counts to samples uses the self-reduction framework of Jerrum, Valiant, and Vazirani [Jerrum et al.(1986)Jerrum, Valiant, and Vazirani, Section 6]. We give the deletion procedure explicitly to retain feasibility on every execution and to track its total-variation and bit-time bounds. It uses Remark 1.1 only through its counting guarantee.
Lemma 10.2. Given a finite simple undirected unweighted graph H_0 whose vertices and edges are explicitly listed, and a rational 0<\tau<1, there is a uniform classical randomized algorithm that reports infeasibility exactly when H_0 has no perfect matching. Otherwise it returns a perfect matching on every execution, and its output law is at total variation distance at most \tau from the uniform perfect-matching law. Its bit running time on every execution is polynomial in the full input encoding length and \tau^{-1}.
Proof. First decide perfect-matching feasibility by the deterministic polynomial-time matching algorithm of Edmonds [Edmonds(1965)]. Report infeasibility if appropriate, and return the empty matching when V(H_0)=\varnothing. Otherwise set m_0=|E(H_0)| and m_*=\max\{1,m_0\}. Choose
The integer t is computed by doubling and exact rational comparison.
Maintain a feasible residual graph H and the already selected edges. Choose the first residual edge e=uv in a fixed deterministic ordering. Perfect matchings of H excluding e are counted by Z(H-e); those including e correspond bijectively, after deleting e, to perfect matchings of H-u-v. Test both child graphs for feasibility exactly. At least one is feasible. If only one is feasible, take it. If both are feasible, make two fresh calls to Remark 1.1, with relative error \eta and failure probability \gamma, obtaining nonnegative rational estimates A for Z(H-u-v) and B for Z(H-e). If A+B=0, take the exclusion child. Otherwise put \widehat p=A/(A+B), draw exactly t fresh fair bits as a uniform integer J\in\{0,\ldots,2^t-1\}, and take the inclusion child precisely when
Replace H by the chosen child. Whenever the inclusion child is taken, including a forced choice, append e to the selected edges. All ratio and floor operations are exact rational or integer operations.
Every chosen child is feasible, regardless of the estimates. Each decision removes at least one residual edge, so there are at most m_0 decisions. When no residual edges remain, feasibility forces the residual vertex set to be empty. The selected edges then form a perfect matching of H_0 on every execution.
For the error bound, compare this process to the ideal deletion sampler that takes the inclusion child with its exact count ratio. These exact ratios telescope, giving the uniform perfect-matching law. At a history where both children are feasible, write their positive counts as z_+ and z_-, with p=z_+/(z_++z_-). When both estimates succeed, write A=z_+(1+a) and B=z_-(1+b), where |a|,|b|\le\eta. Then
The last step uses z_+z_-\le(z_++z_-)^2/4. Fresh call randomness bounds the conditional probability that either estimate fails by 2\gamma, at every adaptive history. On failure the branch law can change by at most one in total variation, while the dyadic floor changes the successful branch probability by at most 2^{-t}. The fallback A+B=0 occurs only on a failed estimate when both true counts are positive. Thus the conditional branch-law error is at most
Forced branches have zero error. Couple the two deletion processes until their prefixes differ. With at most m_0 decisions, the output total-variation error is at most m_0\beta. Since \eta<1/8 and 2^{-t}\le\eta, we have \beta\le4\eta and hence
There are at most 2m_0 counting calls and 2m_0+1 exact feasibility tests, all on simple graphs no larger than H_0. The inverse relative error is 8m_*/\tau, and the logarithmic confidence cost is \log(8m_*/\tau). The every-execution bit bound of Remark 1.1 also bounds the bit lengths of its outputs on failed calls. Therefore the exact ratio and floor computations, the t=O(\log(m_*/\tau)) fresh bits per branch, and all graph updates have bit cost polynomial in the full input length and \tau^{-1} on every execution. No rejection loop or random stopping criterion is used.
Proof of Remark 10.1(ii). For sampling, apply Remark 10.2 to H_f or H_k and decode by keeping the original edges represented by selected cross edges, or by discarding the dummy-incident edges, respectively. Exact feasibility testing of the gadget reports infeasibility precisely for an empty target family. Uniform perfect matchings project to the uniform target law because the fibres in (10.1) and (10.2) are constant across target members. Deterministic decoding cannot increase total variation and takes polynomial time, without enumerating any fibre. Every decoded output is feasible, which proves the sampling assertion.
References
- [Bezáková et al.(2008)Bezáková, Štefankovič, Vazirani, and Vigoda]Ivona Bezáková, Daniel Štefankovič, Vijay V. Vazirani, and Eric Vigoda. Accelerating simulated annealing for the permanent and combinatorial counting problems. SIAM Journal on Computing, 37(5):1429–1454, 2008. doi:10.1137/050644033.
- [Cai and Liu(2020)]Jin-Yi Cai and Tianyu Liu. Counting perfect matchings and the eight-vertex model. In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), volume 168 of Leibniz International Proceedings in Informatics, pages 23:1–23:18. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPIcs.ICALP.2020.23. URL https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.23.
- [Chen et al.(2026a)Chen, Guo, Vigoda, and Yang]Xiaoyu Chen, Heng Guo, Eric Vigoda, and Xiongxin Yang. Fast FPRAS for the permanent. Preprint, arXiv:2609.20717v1, 2026. URL https://arxiv.org/abs/2609.20717v1.
- [Chen et al.(2026b)Chen, Vigoda, and Yang]Xiaoyu Chen, Eric Vigoda, and Xiongxin Yang. Faster FPRAS for the permanent via restricted Poincaré inequalities and coupled flows. Preprint, arXiv:2608.26599v1, 2026. URL https://arxiv.org/abs/2608.26599v1.
- [Edmonds(1965)]Jack Edmonds. Paths, trees, and flowers. Canadian Journal of Mathematics, 17:449–467, 1965. doi:10.4153/CJM-1965-045-4.
- [Efron and Stein(1981)]Bradley Efron and Charles Stein. The jackknife estimate of variance. The Annals of Statistics, 9(3):586–596, 1981. doi:10.1214/aos/1176345462.
- [Fei et al.(2025)Fei, Goldberg, and Lu]Yumou Fei, Leslie Ann Goldberg, and Pinyan Lu. Two-state spin systems with negative interactions. Information and Computation, 307:105340, 2025. doi:10.1016/j.ic.2025.105340.
- [Hastings(1970)]W. K. Hastings. Monte Carlo sampling methods using Markov chains and their applications. Biometrika, 57(1):97–109, 1970. doi:10.1093/biomet/57.1.97.
- [Hoeffding(1963)]Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13–30, 1963. doi:10.1080/01621459.1963.10500830.
- [Jerrum and Sinclair(1989)]Mark Jerrum and Alistair Sinclair. Approximating the permanent. SIAM Journal on Computing, 18(6):1149–1178, 1989. doi:10.1137/0218077.
- [Jerrum et al.(2004)Jerrum, Sinclair, and Vigoda]Mark Jerrum, Alistair Sinclair, and Eric Vigoda. A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. Journal of the ACM, 51(4):671–697, 2004. doi:10.1145/1008731.1008738.
- [Jerrum et al.(1986)Jerrum, Valiant, and Vazirani]Mark R. Jerrum, Leslie G. Valiant, and Vijay V. Vazirani. Random generation of combinatorial structures from a uniform distribution. Theoretical Computer Science, 43:169–188, 1986. doi:10.1016/0304-3975(86)90174-X.
- [Kasteleyn(1963)]P. W. Kasteleyn. Dimer statistics and phase transitions. Journal of Mathematical Physics, 4(2):287–293, 1963. doi:10.1063/1.1703953.
- [Metropolis et al.(1953)Metropolis, Rosenbluth, Rosenbluth, Teller, and Teller]Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, Augusta H. Teller, and Edward Teller. Equation of state calculations by fast computing machines. The Journal of Chemical Physics, 21(6):1087–1092, 1953. doi:10.1063/1.1699114.
- [Sinclair(1992)]Alistair Sinclair. Improved bounds for mixing rates of Markov chains and multicommodity flow. Combinatorics, Probability and Computing, 1:351–370, 1992. URL https://people.eecs.berkeley.edu/~sinclair/flow.pdf.
- [Štefankovič et al.(2018)Štefankovič, Vigoda, and Wilmes]Daniel Štefankovič, Eric Vigoda, and John Wilmes. On counting perfect matchings in general graphs. In Michael A. Bender, Martín Farach-Colton, and Miguel A. Mosteiro, editors, LATIN 2018: Theoretical Informatics, volume 10807 of Lecture Notes in Computer Science, pages 873–885. Springer, 2018. doi:10.1007/978-3-319-77404-6_63. Full version: arXiv:1712.07504v1. URL https://arxiv.org/abs/1712.07504v1.
- [Swendsen and Wang(1986)]Robert H. Swendsen and Jian-Sheng Wang. Replica Monte Carlo simulation of spin-glasses. Physical Review Letters, 57(21):2607–2609, 1986. doi:10.1103/PhysRevLett.57.2607.
- [Tutte(1954)]W. T. Tutte. A short proof of the factor theorem for finite graphs. Canadian Journal of Mathematics, 6:347–352, 1954. doi:10.4153/CJM-1954-033-3.
- [Valiant(1979)]Leslie G. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8(2):189–201, 1979. doi:10.1016/0304-3975(79)90044-6.
- [Wang and Swendsen(2005)]Jian-Sheng Wang and Robert H. Swendsen. Replica Monte Carlo simulation (revisited). Progress of Theoretical Physics Supplement, 157:317–323, 2005. doi:10.1143/PTPS.157.317. Preprint version: https://arxiv.org/abs/cond-mat/0407273v1.
- [Yi(2026)]Zihong Yi. Diffuse Gaussian truncation for deterministic approximate counting. Preprint, arXiv:2609.04079v1, 2026. URL https://arxiv.org/abs/2609.04079v1.