A D V E R T |
I S E M E N T |
| Math Sites: lean ages 13-∞ readme referees parents | >>> MAITH GAMES <<< | all 372 compute stand |
|
LEVEL 2 OF 2 · Approximate counting of common integer polymatroid bases
Approximate counting of common bases of two matroids
expertly designed by an internal OpenAI model · released 2026-09-23
· original PDF
IntroductionA matroid \(M\) on a finite set \(E\) is a family \(\mathcal I\) of independent sets containing \(\varnothing\), closed under taking subsets, and satisfying augmentation: if \(I,J\in\mathcal I\) and \(|I|<|J|\), then \(I\cup\{e\}\in\mathcal I\) for some \(e\in J\setminus I\). The rank of \(A\subseteq E\) is the largest size of an independent subset of \(A\). A basis is a maximal independent subset of \(E\); augmentation implies that all bases have size \(\operatorname{rk}_M(E)\). An independence oracle reports whether a queried subset is independent. Our input consists of two matroids \(M_1,M_2\) of the same rank \(r\) on the explicitly enumerated ground set \([n]=\{1,\ldots,n\}\), supplied by fixed exact independence oracles. Each query is an \(n\)-bit subset indicator. We count an oracle call separately from the bit operations needed to construct the query and process the answer. Writing \(\mathcal B(M)\) for the set of bases of \(M\), the quantity to be estimated is \[Z(M_1,M_2)=|\mathcal B(M_1)\cap\mathcal B(M_2)|.\] The required approximation has relative error at most \(\epsilon\) with failure probability at most \(\delta\). A fully polynomial randomized approximation scheme, or FPRAS, achieves this guarantee with polynomial dependence on the input size, \(\epsilon^{-1}\), and \(\log\delta^{-1}\). We prove such a result in the oracle model, with a work bound on every execution rather than only in expectation. Theorem 1. There is a single randomized oracle algorithm with the following guarantee. Given independence oracles for arbitrary rank-\(r\) matroids \(M_1,M_2\) on \([n]\), and rational \(\epsilon,\delta\in(0,1)\), it outputs a nonnegative rational \(\widehat Z\) such that \[\mathbb P\bigl[(1-\epsilon)Z(M_1,M_2)\le\widehat Z \le(1+\epsilon)Z(M_1,M_2)\bigr]\ge1-\delta.\] If \(Z(M_1,M_2)=0\), its output is always zero. On every execution, the number of oracle calls and the number of other bit operations are bounded by a fixed polynomial in \[n,\qquad \ell,\qquad \epsilon^{-1},\qquad \log\delta^{-1},\] where \(\ell\) is the binary encoding length of \(n,r,\epsilon,\delta\). The algorithm uses only independent unbiased random bits and does not require a representation of either matroid. The theorem also yields an FPRAS for counting common independent sets of prescribed, unrestricted, or maximum cardinality, even when the two matroid ranks differ, and an almost-uniform sampler for each of these families. The sampler decides emptiness exactly and, for a nonempty family, returns a feasible member on every execution, with polynomial dependence on the inverse total-variation tolerance. The full counting and sampling guarantees are stated and proved in 10 in 9. Background and significance.Matroid intersection admits a deterministic polynomial-time optimization algorithm in the independence-oracle model [14, 20]. Counting common bases contains two prominent special cases. Taking the matroids equal gives the number of bases of one matroid. For a bipartite graph with equal vertex-class sizes, take the ground set to be its edges and impose, in each matroid, the constraint of using at most one edge at each vertex on one side. These are partition matroids. When there are no isolated vertices, their common bases are exactly the perfect matchings; an isolated vertex makes that matching count zero. Jerrum, Sinclair, and Vigoda gave an FPRAS for the permanent of a nonnegative matrix, which includes this bipartite matching problem [16]. For a single matroid, early sampling and counting results relied on negative dependence. Feder and Mihail established efficient sampling and approximate counting for balanced matroids, including regular matroids [15]. Anari, Oveis Gharan, and Rezaei later proved rapid mixing for homogeneous strongly Rayleigh distributions [5]. The latter condition requires a fixed-cardinality distribution whose multiaffine generating polynomial is real stable, meaning that it is nonzero whenever all variables have positive imaginary parts. These hypotheses do not hold for all matroids. Anari, Liu, Oveis Gharan, and Vinzant removed such restrictions for single-matroid counting by developing high-dimensional walks for log-concave polynomials, obtaining an independence-oracle FPRAS [3]. For intersections, earlier approaches gave coarser approximations or required additional algebraic information. Barvinok and Samorodnitsky used random linear optimization to obtain coarse estimates of logarithms of set-system cardinalities; their optimization-oracle framework applies to common bases through matroid intersection [7]. Anari and Oveis Gharan obtained exponential-factor approximations from real-stable polynomials supplied by evaluation oracles [4]; Straszak and Vishnoi developed capacity bounds with stability and representation-dependent qualifications [21]. Such polynomial evaluations are not furnished by an independence oracle. Anari, Oveis Gharan, and Vinzant then gave a deterministic polynomial-time \(2^{O(r)}\)-factor approximation for common bases of arbitrary rank-\(r\) independence-oracle matroids [6]. Their relative-approximation scheme has \(2^{O(r)}\) dependence in its running time, so it becomes fully polynomial when \(r=O(\log n)\) but does not give an unrestricted-rank FPRAS [6]. Efficient sampling and approximate counting were also obtained for strongly Rayleigh distributions under a constant number of partition constraints, with access to individual coefficients and a suitable initial support element [2]. Neither the constant number of parts nor the stronger stability hypothesis is available for the arbitrary paired matroid construction used here. Cryan, Guo, and Mousa explicitly asked for a rapidly convergent Markov chain for uniform sampling of common bases or common independent sets [12]. The question of an FPRAS for two arbitrary independence-oracle matroids is explicitly recorded in Liu’s dissertation [19]. 1 gives an affirmative answer to that formulation. Proof strategy.We encode a common basis as a basis of a rank-\(n\) matroid on \(2n\) elements that chooses one element from each of \(n\) prescribed pairs. To maintain strictly positive weights, an \(n\)-set \(S\) of rank deficiency \(d=n-\operatorname{rk}(S)\) receives weight \(q^d\), with \(q\) decreasing from \(1\) to an exponentially small rational. An \(n\)-set choosing one element from every pair is called a transversal. The total weight of transversals is initially known and approaches the desired count as \(q\) decreases. The chain must move between transversals whose selected elements may differ in many pairs. Nonbasis transversals can have very small weight, so positivity and connectivity alone do not give the polynomial quantitative bounds needed for counting. We enlarge the state space by allowing one empty pair and one doubly occupied pair; their ordered indices specify a defect type. A positive multiplier for each type balances its total weight against the transversal total. The chain makes one-element exchanges, with Metropolis acceptance probabilities determined by these multiplied weights. Balancing defect classes and learning their weights through interpolation follows the permanent algorithm of Jerrum, Sinclair, and Vigoda [16]. The algebraic input is the homogeneous Tutte theorem of Brändén and Huh [9]. Applied to the matroid and its dual, it yields two complementary tools: inequalities between defect totals, and a transport inequality between conditional distributions. The transport compares two choices of a missing slot in a partition into singleton and two-element slots. It recursively assigns balanced signed demands, bounds the cost of splitting a slot by a quadratic form with at most one positive direction, and realizes the final demands by exchange flows. Transport between conditional laws also underlies the local Poincaré framework of Chen, Feng, Ju, Miao, Yin, and Zhang [10]. Here the transport is constructed by signed currents whose energy is controlled by the omitted-element quadratic forms. These tools bound variation visible on individual transversals and on the means of defect types. They need not bound arbitrary variation within a defect type. This distinction dictates the simulation argument: we prove rapid mixing for the trace, which records successive visits to transversals, and a separate variance bound for the type indicators and ratio observables actually averaged by the algorithm. Chen, Vigoda, and Yang used partition-restricted Poincaré inequalities to control hole-pattern frequency estimates in the permanent algorithm [11]. Here the variance bound also retains individual transversal values, and we combine it with trace mixing. A warm start is a starting law bounded pointwise by a controlled multiple of the stationary law. Fresh independent restarts along the annealing schedule supply these starts even though the multipliers are learned adaptively from earlier observations. All partition sums, conditioning trees, and flows appearing in the proof are analytical devices. The algorithm evaluates individual state weights by oracle rank computations and learns the required multipliers from observations of an explicit chain. Organization.2 gives the paired reduction and the positive weights. 3 derives the quadratic signature inequalities, and 4 proves the missing-slot transport bound. 5 obtains transversal variance and the observable Poincaré inequality. 6 turns them into time-average and trace-chain estimates. 7 assembles the annealing algorithm and analyzes its error, and 8 establishes the bounded-bit oracle implementation and completes the proof of 1. 9 derives the counting and sampling consequences for common independent sets. The paired-ground-set reductionWe first replace common bases by transversal bases of one matroid. This gives a single rank-deficiency weight that can be evaluated using the two input oracles. The positive-weight state space will contain all transversals and all sets with one empty pair and one full pair. Augmentation implies that every maximal independent subset of \(A\) has size \(\operatorname{rk}_M(A)\). Thus a greedy scan computes an original matroid’s rank with at most \(n\) independence queries. The dual matroid \(M^*\) has as bases the complements of the bases of \(M\), and its rank is \[ \operatorname{rk}_{M^*}(A)=|A|-\operatorname{rk}_M(E)+\operatorname{rk}_M(E\setminus A). \tag{1}\] Indeed, extending a maximal independent subset of \(E\setminus A\) to a basis minimizes the number of basis elements in \(A\); this minimum is \(\operatorname{rk}_M(E)-\operatorname{rk}_M(E\setminus A)\). Maximizing the number of elements of \(A\) in a basis complement gives (1). Make two copies of \([n]\), with corresponding elements denoted \(x_i,y_i\), and use the paired reduction of Anari, Oveis Gharan, and Vinzant [6]: \[V=\{x_1,y_1,\ldots,x_n,y_n\},\qquad K=M_1\oplus M_2^*.\] Here \(M_1\) is on the \(x\)-copy and \(M_2^*\) on the \(y\)-copy. The matroid \(K\) has rank \(n\); a set is independent in this direct sum exactly when its restrictions to the two copies are independent in their respective matroids. A transversal is an \(n\)-set that contains exactly one element of each pair \(\{x_i,y_i\}\). For \(A\subseteq[n]\), the associated transversal is \[S(A)=\{x_i:i\in A\}\cup\{y_i:i\notin A\}.\] It is a basis of \(K\) if and only if \(A\) is a basis of both \(M_1\) and \(M_2\). To see this, independence of an \(n\)-set in the direct sum forces each summand to attain its rank, and dual bases are basis complements. If \(n=0\), the algorithm returns \(1\). Otherwise, the deterministic matroid-intersection algorithm tests whether a common independent set of size \(r\) exists; if none exists, we return \(0\). This algorithm uses polynomially many independence queries and polynomial additional work [20]; the promised matroid axioms, exact oracles, and explicit ground set are its required input hypotheses. Henceforth \[ n\ge1,\qquad Z(M_1,M_2)\ge1. \tag{2}\] For \(0<q\le1\) and every \(S\in\binom Vn\), define \[ d(S)=n-\operatorname{rk}_K(S),\qquad f_q(S)=q^{d(S)}. \tag{3}\] These weights are strictly positive. Let \(\Omega_0\) be the set of all transversals. Fixed-cardinality weights proportional to \(q^{-\operatorname{rk}(S)}\) already appear in the log-concave-polynomial framework of Anari, Liu, Oveis Gharan, and Vinzant [3]. Here the additional restriction to paired occupancy classes is central. For distinct \(i,j\in[n]\), let \(\Omega_{ij}\) consist of the \(n\)-sets for which pair \(i\) is empty, pair \(j\) is full, and every other pair is singly occupied. Set \[ \mathcal T=\{0\}\cup\{ij:i,j\in[n],\ i\ne j\},\qquad \Omega=\bigsqcup_{T\in\mathcal T}\Omega_T,\qquad c_T(q)=\sum_{S\in\Omega_T}f_q(S). \tag{4}\] The order of the indices in \(ij\) matters. In particular, \(c_0(q)\) sums over all transversals, including those that are not bases. We suppress \(q\) when it is fixed. Quadratic signature inequalitiesThe counting argument uses two consequences of the rank weights: relations between the total weights of defect types, and a quadratic bound for the transport construction. Both follow from a single signature property, applied to the polynomial of selected elements and to the polynomial of omitted elements. We use the following consequence of the Lorentzian theory. A polynomial has the quadratic signature property if every homogeneous quadratic obtained from it by partial differentiation and nonnegative linear substitutions has a Hessian with at most one positive eigenvalue. The zero polynomial is allowed, as are substitutions that identify variables or set them to zero. Coefficients throughout this section are nonnegative. Theorem 2 (Brändén–Huh). For a matroid \(N\) on a ground set \(E\) and \(0<q\le1\), the polynomial \[T_{q,N}(z_0,z)=\sum_{A\subseteq E} q^{-\operatorname{rk}_N(A)}z_0^{|E|-|A|}\prod_{a\in A}z_a\] is Lorentzian. Lorentzian polynomials are closed under partial derivatives and nonnegative linear substitutions, and a quadratic Lorentzian polynomial has a Hessian with at most one positive eigenvalue. In particular, \(T_{q,N}\) has the quadratic signature property. The statements used here are [9], together with the defining quadratic signature. We need no other facts about Lorentzian polynomials. The connection between derivative Hessians and spectral estimates for matroid walks was developed by Anari, Liu, Oveis Gharan, and Vinzant [3]. Here we use the quadratic forms to construct transport on the restricted paired state space. Write \(z^S=\prod_{a\in S}z_a\) and form \[ F(z)=\sum_{S\in\binom Vn} f_q(S)z^S, \qquad F^\vee(z)=\sum_{S\in\binom Vn}f_q(V\setminus S)z^S. \tag{5}\] Both have the quadratic signature property. Indeed, \[F=\frac{q^n}{n!}\left.\partial_{z_0}^{\,n}T_{q,K}\right|_{z_0=0}.\] Since \(|V|=2n\) and \(\operatorname{rk}K=n\), (1) gives \(\operatorname{rk}_{K^*}(S)=\operatorname{rk}_K(V\setminus S)\) for \(|S|=n\); the same formula with \(K^*\) gives \(F^\vee\). We will repeatedly extract the coefficient of exponent exactly one in a variable, deleting that variable. This operation is \(G\mapsto(\partial_zG)|_{z=0}\), so it preserves the quadratic signature property. In particular, after identifying the two variables of a pair, it imposes exactly one selected element in that pair. Relations between defect totalsWe first derive inequalities that remain valid after fixing any partial transversal. They will control the choice of a conditioning pair and the cost of transferring a defect mean to a transversal mean. A partial transversal assignment \(\sigma\) prescribes one element in each of some pairs, requiring its inclusion and its mate’s exclusion. Let \(z_{\sigma}\) be the total weight of transversals respecting \(\sigma\). For distinct unassigned pairs \(i,j\), let \(c^{\sigma}_{ij}\) be the total weight respecting \(\sigma\) with pair \(i\) empty, pair \(j\) full, and all other unassigned pairs singly occupied. The empty assignment has \(z_\varnothing=c_0\) and \(c^\varnothing_{ij}=c_{ij}\). All these totals are positive. Lemma 3. For distinct unassigned indices \(i,j\), \[ 4c^{\sigma}_{ij}c^{\sigma}_{ji}\le z_{\sigma}^2. \tag{6}\] For distinct unassigned indices \(i,j,k\), \[ c^{\sigma}_{ij}c^{\sigma}_{jk}\le z_{\sigma}c^{\sigma}_{ik}. \tag{7}\] Proof. In \(F\), differentiate in the elements selected by \(\sigma\), set both variables of each assigned pair to zero, and identify the two variables in every unassigned pair. The resulting polynomial has \(z_{\sigma}\) and \(c^{\sigma}_{ij}\) as the coefficients of the corresponding occupancy patterns. For the first inequality, extract exponent one in all variables other than \(i,j\). The remaining quadratic has Hessian \[\begin{pmatrix}2c^{\sigma}_{ji}&z_{\sigma}\\z_{\sigma}&2c^{\sigma}_{ij}\end{pmatrix}.\] Its positive diagonal and at-most-one-positive-eigenvalue property force its determinant to be nonpositive. For the second inequality, extract exponent one in all variables other than \(i,j,k\), and then differentiate once in the variable of pair \(k\). The Hessian \(A\) of the resulting quadratic satisfies \[ A_{jj}=2c^{\sigma}_{ij},\quad A_{ik}=2c^{\sigma}_{jk},\quad A_{ij}=z_{\sigma},\quad A_{jk}=2c^{\sigma}_{ik}. \tag{8}\] Here and below we use the elementary fact that, if a real symmetric form \(A\) has at most one positive eigenvalue and \(e^\top Ae>0\), then it is negative semidefinite on \(\{v:v^\top Ae=0\}\). A positive vector in that orthogonal subspace would otherwise span with \(e\) a positive definite two-dimensional subspace. This is the one-positive-direction form of the reverse Cauchy–Schwarz principle; see [8]. Apply this fact with \(e=e_j\), since \(A_{jj}>0\). The Schur complement \[B_{uv}=A_{uv}-\frac{A_{uj}A_{jv}}{A_{jj}} \qquad(u,v\in\{i,k\})\] is negative semidefinite. Cauchy–Schwarz for \(-B\) and nonnegativity of the entries of \(A\) give \[\begin{align*} A_{ik} &\le\frac{A_{ij}A_{jk}}{A_{jj}} +\sqrt{\left(\frac{A_{ij}^2}{A_{jj}}-A_{ii}\right) \left(\frac{A_{jk}^2}{A_{jj}}-A_{kk}\right)}\\ &\le 2\frac{A_{ij}A_{jk}}{A_{jj}}. \end{align*}\] Substituting (8) proves the second inequality. ◻ A transport inequalityOur goal is to bound the difference of two weighted means by the energy of one-element exchanges. The two classes differ in which singleton slot is missing. Allowing holes in the other slots makes it possible to connect these classes with a controlled signed flow. Fix \(q\in(0,1]\) and write \(f=f_q\) throughout this section. We state the main lemma in a form that permits conditioning and regrouping elements into slots. Its proof uses only the quadratic signature property of \(F^\vee\) and positivity of \(f\). Partition \(V\) into fixed included elements \(B\), fixed excluded elements \(C\), two distinct singleton slots \(p,d\), and \(m\) ordinary two-element slots \(E_1,\ldots,E_m\). We identify each singleton slot with its element. Assume \[ |B|+1+m=n. \tag{9}\] It follows that \(|C|=n-1-m\). The slots need not be pairs from the original pairing. In particular, \(p,d\) may lie in the same original pair. Let \(\mathcal X\) consist of the \(n\)-sets obtained by including \(B\), excluding \(C\), leaving exactly one of the \(m+2\) slots empty, and selecting one element from each other slot. For a missing slot \(h\), write \(\mathcal X_h\) for its class and let \(h(S)\) be the missing-slot label of \(S\). Give each slot \(h\) a positive multiplier \(W_h\); a vertex \(S\in\mathcal X_h\) has multiplied weight \(W_hf(S)\). For an element \(i\in E_t\), also write \(W_i=W_t\); for \(i=p\) or \(i=d\), \(W_i\) is the multiplier of that singleton slot. Join two vertices whenever they differ by one element exchange, and give each undirected edge conductance \[\kappa(S,S')=\min\{W_{h(S)}f(S),W_{h(S')}f(S')\}.\] For \(H:\mathcal X\to\mathbb R\), put \[D_{\mathcal X}(H)=\sum_{\{S,S'\}\text{ edge}} \kappa(S,S')\bigl(H(S)-H(S')\bigr)^2.\] Let \(s_p,s_d\) be the unmultiplied weight totals of \(\mathcal X_p\) and \(\mathcal X_d\), and let \(\overline H_p,\overline H_d\) be the means of \(H\) on these classes with weights \(f\). For each ordinary slot \(t\), let \(v_t\) be the total weight of the \(n\)-sets that include \(B\), exclude \(C\), miss both \(p\) and \(d\), contain both elements of \(E_t\), and contain one element of each other ordinary slot. These latter sets define totals only; they need not belong to \(\mathcal X\). The subscript \(t\) records the doubled ordinary slot in \(v_t\) and the missing ordinary slot in \(\mathcal X_t\). Lemma 4 (Transport). With the notation above, \[ (\overline H_p-\overline H_d)^2 \le \left(\frac1{s_pW_p}+\frac1{s_dW_d} +\frac2{s_ps_d}\sum_{t=1}^m\frac{v_t}{W_t}\right) D_{\mathcal X}(H). \tag{10}\] Proof. Orient the edges arbitrarily. We seek a signed edge flow \(J\) whose divergence (net outgoing current) at \(S\) is \(f(S)/s_p\) on \(\mathcal X_p\), \(-f(S)/s_d\) on \(\mathcal X_d\), and zero elsewhere. Summation by parts and Cauchy–Schwarz would then give \[ \begin{split} (\overline H_p-\overline H_d)^2 &=\left(\sum_{e=(S,S')}J(e)(H(S)-H(S'))\right)^2\\ &\le\left(\sum_e\frac{J(e)^2}{\kappa(e)}\right)D_{\mathcal X}(H), \end{split} \tag{11}\] where each undirected edge occurs once with its chosen orientation. It suffices to bound this flow energy by the coefficient in (10). This passage from a signed flow to an energy bound is the standard electrical-network duality [13]. We first assign balanced demands recursively and then route them within cliques at the leaves. Process the ordinary slots in the order \(1,\ldots,m\). A recursive system of balanced demands.After \(k\) slots have been processed, a node of the recursion is a set \[R=\{p,d\}\cup\{a_1,\ldots,a_k\},\qquad a_t\in E_t.\] For each \(i\in R\), let \(s_i(R)\) be the total weight of the sets that include \(B\cup(R\setminus\{i\})\), contain no other elements of the displayed slots, and choose one element from each unprocessed slot. The elements of \(C\) remain excluded. We associate real numbers \(h_i(R)\) to the holes \(i\in R\) and maintain balance \[ \sum_{i\in R}s_i(R)h_i(R)=0. \tag{12}\] At the root, \(R=\{p,d\}\), set \(h_p=1/s_p\) and \(h_d=-1/s_d\). The quantity \(s_i(R)h_i(R)\) is the signed demand assigned to hole \(i\); thus \(h_i(R)\) is demand per unit weight. Suppose that the next slot is \(E_t=\{a,b\}\). The two child nodes are \(R\cup\{a\}\) and \(R\cup\{b\}\). For an old hole \(i\in R\), abbreviate \(s_i^l=s_i(R\cup\{l\})\), so that \[s_i^a+s_i^b=s_i(R).\] The new-hole totals \(s_a(R\cup\{a\})\) and \(s_b(R\cup\{b\})\) count the same sets: all of \(R\) is included and slot \(E_t\) is empty. Denote their common positive value by \(u\). Keep \(h_i\) unchanged for old holes, and define \[ h_l(R\cup\{l\})=-\frac1u\sum_{i\in R}h_i(R)s_i^l, \qquad l\in\{a,b\}. \tag{13}\] Balance holds in both children. The two newly introduced values have sum zero, by balance in the parent. Define the potential at level \(k\) by \[\Phi_k=\sum_{R\text{ at level }k}\ \sum_{i\in R} \frac{s_i(R)h_i(R)^2}{W_i}.\] At the leaves this quantity will bound the energy needed to realize the demands. Write \(X=\sum_{i\in R}h_i(R)s_i^a\) for the current split. The two new values are \(-X/u\) and \(X/u\). Old-hole contributions are conserved, so the contribution of this split to the potential increase is \(2X^2/(uW_t)\). We next bound this cost by a quadratic form. The quadratic bound on each split.For an unprocessed slot \(t\), define a symmetric matrix \(V_t(R)\) on \(R\), with zero diagonal. For \(i\ne j\), its \(ij\) entry is the weight total obtained by including \(B\cup(R\setminus\{i,j\})\), including both elements of \(E_t\), and choosing one element from each other unprocessed slot; all other displayed elements and all of \(C\) are excluded. At the root, \[ (V_t(\{p,d\}))_{pd}=v_t. \tag{14}\] For the next slot \(E_t=\{a,b\}\), construct a quadratic from \(F^\vee\), whose variables record omitted elements. Differentiate in \(C\) and in the unchosen element of each of the \(k\) processed slots, and set these variables and the variables of \(B\) to zero. In each unprocessed slot other than \(t\), identify its two variables and extract exponent one. The remaining degree is \[n-(n-1-m+k)-(m-k-1)=2.\] Call its Hessian \(A\). Its active variables are exactly \(R\cup\{a,b\}\). They have not been identified and remain multiaffine, so every diagonal entry of \(A\) is zero. The off-diagonal entries are read as follows; here \(i,j\in R\) are distinct, and every active element not listed as omitted is selected: \[ \begin{array}{c|c|c} \text{active omissions}&\text{selected elements of }E_t&\text{Hessian entry}\\ \hline i,j&a,b&A_{ij}=(V_t(R))_{ij}\\ i,b&a&A_{ib}=s_i^a\\ i,a&b&A_{ia}=s_i^b\\ a,b&\varnothing&A_{ab}=u \end{array} \tag{15}\] Thus \(V_t(R)\) is the old–old block of \(A\), and \(A\) has at most one positive eigenvalue by the quadratic signature property. Let \(e=e_a+e_b\). Then \(e^\top Ae=2u>0\), so \(A\) is negative semidefinite on its \(A\)-orthogonal complement. Extend \(h=(h_i(R))_{i\in R}\) by zero on \(a,b\). Both \(h\) and \(e_a-e_b\) lie in this orthogonal complement: for \(h\) this is (12), and for \(e_a-e_b\) it follows from the zero diagonals. With \(X\) as defined above, we have \[h^\top A(e_a-e_b)=-2X,\qquad (e_a-e_b)^\top A(e_a-e_b)=-2u.\] Cauchy–Schwarz for the negated form therefore gives \[ \frac{2X^2}{u}\le-h^\top V_t(R)h. \tag{16}\] This is a bound on the cost of introducing the new hole. It uses nonpositivity only on the \(A\)-orthogonal complement of \(e\), not on the entire space of hole values. A conserved quantity for future slots.If \(t'\) is processed later than \(t\), then \[ \sum_{l\in\{a,b\}} h(R\cup\{l\})^\top V_{t'}(R\cup\{l\})h(R\cup\{l\}) =h(R)^\top V_{t'}(R)h(R). \tag{17}\] For entries between old holes, the two child totals add to the parent total because slot \(t\) is singly occupied. An entry between an old hole and the new hole is the same in both children: slot \(t\) is then empty. The corresponding cross terms cancel because the two new \(h\) values are opposite. The new diagonal is zero. This proves the identity. Thus the quadratic expression for a future slot is conserved when an earlier slot is split. The potential itself can increase; the identity lets us sum the bounds for that increase using the original root data. By (16), the potential increase at node \(R\) is at most \(-h(R)^\top V_t(R)h(R)/W_t\). Repeated use of (17) gives, just before slot \(t\) is processed, \[\sum_{R\text{ at level }t-1}h(R)^\top V_t(R)h(R) =h(\{p,d\})^\top V_t(\{p,d\})h(\{p,d\}) =-\frac{2v_t}{s_ps_d}.\] The total increase at this level is therefore at most \(2v_t/(s_ps_dW_t)\). Summing over the slots gives \[ \Phi_m\le\Phi_0+\frac2{s_ps_d}\sum_{t=1}^m\frac{v_t}{W_t} =\frac1{s_pW_p}+\frac1{s_dW_d} +\frac2{s_ps_d}\sum_{t=1}^m\frac{v_t}{W_t}. \tag{18}\] Realizing the demands by edge flows.At a leaf \(R\), each hole \(i\in R\) gives the vertex \(S_i=B\cup(R\setminus\{i\})\), and \(s_i(R)=f(S_i)\). These vertices form a clique of allowed exchanges. Give \(S_i\) prescribed divergence \(g_i=f(S_i)h_i(R)\); their sum is zero. Choose a hub maximizing \(W_if(S_i)\). On the edge from each nonhub \(S_i\) to the hub, send signed current \(g_i\). The hub automatically has the prescribed divergence, and the energy of this clique flow is \[\sum_{i\text{ nonhub}}\frac{g_i^2}{W_if(S_i)} \le\sum_{i\in R}\frac{f(S_i)h_i(R)^2}{W_i}.\] Every used edge determines its leaf: the union of its endpoints is \(B\cup R\). Thus distinct leaf flows use disjoint edges, and their total energy is at most \(\Phi_m\). Edges that flip a selected element within an ordinary slot without changing the hole are unused. An endpoint vertex in \(\mathcal X_p\) or \(\mathcal X_d\) has a unique leaf representation. Its divergence is respectively \(f(S)/s_p\) or \(-f(S)/s_d\), since the root values of \(h_p,h_d\) never change. A vertex missing an ordinary slot has exactly two leaf representations, corresponding to the two choices of the element of that slot in \(R\). These representations have the same choices in every other slot and therefore the same recursion prefix before their missing slot is processed. Their two \(h\) values were introduced with opposite signs in (13) and thereafter remained unchanged; the vertex weight \(f(S)\) is the same in both representations. Its divergences cancel. 1 shows this cancellation and the distinction between shared vertices and disjoint used edges. The resulting flow has the required divergences and energy at most \(\Phi_m\). Equations (11) and (18) prove (10). The construction also covers \(m=0\), when there is only the root clique. ◻ A chain and its observable Poincaré boundWe now apply transport to a Metropolis chain on transversals and defect states. The target is a variance bound that retains all values on transversals and only the mean within each defect class. We prove its two components separately before combining them. Fix \(q\in(0,1]\). For each defect type \(ij\), choose a positive multiplier \(w_{ij}\), and define \[ \lambda(S)= \begin{cases} f_q(S),&S\in\Omega_0,\\ w_{ij}f_q(S),&S\in\Omega_{ij}, \end{cases} \qquad \Lambda=\sum_{S\in\Omega}\lambda(S),\qquad \pi(S)=\frac{\lambda(S)}\Lambda. \tag{19}\] The conditional law on transversals is \(\mu(S)=f_q(S)/c_0\) for \(S\in\Omega_0\); it does not depend on the multipliers. Call the multipliers good if \[ \frac14w^*_{ij}\le w_{ij}\le4w^*_{ij}, \qquad w^*_{ij}=\frac{c_0}{c_{ij}}. \tag{20}\] For good multipliers, \[ \Lambda\le5n^2c_0,\qquad \pi(\Omega_0)\ge\frac1{5n^2},\qquad \pi(\Omega_{ij})\ge\frac1{20n^2}. \tag{21}\] Indeed each defect has total multiplied weight between \(c_0/4\) and \(4c_0\), and there are \(n(n-1)\) defects. The Metropolis chain.At a state \(S\), stay put with probability \(1/2\). Otherwise choose uniformly and independently \(a\in S\) and \(b\in V\setminus S\), and propose \(S'=S\setminus\{a\}\cup\{b\}\). Reject if \(S'\notin\Omega\); otherwise accept with probability \(\min\{1,\lambda(S')/\lambda(S)\}\). Write \(P\) for its transition matrix. This is a reversible chain with stationary law \(\pi\). It is irreducible: any two transversals are connected by flips within pairs, and each defect can reach a transversal by moving an element from its full pair to its empty pair. All these transitions have positive probability. It is lazy, with \(P(S,S)\ge1/2\). For \(H:\Omega\to\mathbb R\), define the unnormalized energy \[ D(H)=\sum_{\substack{\{S,S'\}\\S,S'\in\Omega,\ |S\triangle S'|=2}} \min\{\lambda(S),\lambda(S')\}\bigl(H(S)-H(S')\bigr)^2. \tag{22}\] Each undirected edge is counted once. The Dirichlet form is \[ \mathcal E(H)=\langle H,(I-P)H\rangle_\pi=\frac{D(H)}{2n^2\Lambda}. \tag{23}\] Here \(\langle G,H\rangle_\pi=\sum_S\pi(S)G(S)H(S)\). Variation on transversalsThe first application recursively conditions the transversal law. At each node, the defect-total inequalities select a pair for which the transport coefficient is bounded, and variance decomposition assembles the resulting estimates. Lemma 5. For good multipliers and every \(H:\Omega\to\mathbb R\), \[ \operatorname{Var}_\mu H\le C_{\rm p}\frac{D(H)}{c_0}, \qquad C_{\rm p}=n(1+8n). \tag{24}\] Proof. We construct a binary tree that successively conditions the transversal law. We choose each branching pair to control the transport coefficient at that node. At a node with partial assignment \(\sigma\), set \[a_{ij}=\frac{c^{\sigma}_{ij}}{z_{\sigma}}\frac{c_{ji}}{c_0} \quad (i\ne j\text{ unassigned}).\] 3, used both conditionally and with the global indices reversed, gives \[ a_{ij}a_{ji}\le\frac1{16},\qquad a_{ij}a_{jk}\le a_{ik}\quad(i,j,k\text{ distinct}). \tag{25}\] Draw an arc \(i\to j\) when \(a_{ij}>1\). There is no two-cycle, and arcs are transitive on distinct vertices. A shortest directed cycle of length at least three would therefore have a shorter cycle. The graph is acyclic and has a sink \(k\). Thus \[ \frac{c^{\sigma}_{kt}}{z_{\sigma}}\frac{c_{tk}}{c_0}\le1 \quad\text{for every other unassigned pair }t. \tag{26}\] If only one pair remains, take that pair and the condition is vacuous. Branch by specifying which element of pair \(k\) is chosen. Apply 4 with the assignment \(\sigma\) fixed, the two elements of pair \(k\) as singleton slots \(p,d\), and the other unassigned pairs as ordinary slots. The class \(\mathcal X_p\) selects \(d\), and \(\mathcal X_d\) selects \(p\). They are the two children, so \(s_p+s_d=z_{\sigma}\) and \(W_p=W_d=1\). If ordinary slot \(t\) is empty, pair \(k\) is full; hence \(W_t=w_{tk}\). Also \(v_t=c^{\sigma}_{kt}\). Goodness and (26) imply \[ \frac{v_t}{W_t}\le4\frac{c^{\sigma}_{kt}c_{tk}}{c_0}\le4z_{\sigma}. \tag{27}\] Let \(D_{\sigma}(H)\) be the sum in (22) over all edges whose endpoints respect \(\sigma\). The transport graph is a subgraph of this graph with the same unnormalized conductances. Multiplying (10) by \(s_ps_d/z_{\sigma}\) therefore yields \[ \frac{s_ps_d}{z_{\sigma}}(\overline H_p-\overline H_d)^2 \le\left(1+\frac2{z_{\sigma}}\sum_t\frac{v_t}{W_t}\right)D_{\sigma}(H) \le(1+8n)D_{\sigma}(H). \tag{28}\] Unnormalized variance decomposition at every node says that \(c_0\operatorname{Var}_\mu H\) is the sum of the left side of (28) over all internal nodes; the leaves are singleton transversals. At any fixed depth, the sets of vertices respecting different nodes are disjoint. Indeed, two nodes inherit contradictory choices at the pair where their paths first diverged, even though later choices of branching pair may differ. Hence the sum of \(D_{\sigma}(H)\) at that depth is at most \(D(H)\). There are \(n\) internal depths, giving (24). ◻ Means of defect classesThe second application connects a whole defect class to a transversal event of probability at least one quarter. The preceding variance bound then connects that conditional mean to the full transversal mean. Let \(\overline H_T=\mathbb E_\pi[H\mid\Omega_T]\). Within each type the multiplier is constant, so this is also the conditional mean for unmultiplied weights \(f_q\). Lemma 6. Assume the multipliers are good, and let \(H:\Omega\to\mathbb R\). For each defect type \(ij\) there is an event \(\mathcal A\subseteq\Omega_0\) obtained by prescribing the selected elements in pairs \(i,j\), with \(\mu(\mathcal A)\ge1/4\). Its conditional mean \(\overline H'=\mathbb E_\mu[H\mid\mathcal A]\) satisfies \[ (\overline H_{ij}-\overline H')^2 \le C_{\rm d}\frac{D(H)}{c_0}, \qquad C_{\rm d}=8+32n, \tag{29}\] and \[ (\overline H'-\overline H_0)^2\le4\operatorname{Var}_\mu H. \tag{30}\] Proof. Among the four assignments at pairs \(i,j\), choose one whose transversal total is at least \(c_0/4\). Denote its chosen elements by \(a_i,a_j\) and their mates by \(b_i,b_j\), and let \(\mathcal A\) be this transversal event. In 4, set \[B=\{a_j\},\qquad C=\{b_i\},\qquad p=a_i,\qquad d=b_j,\] and use the remaining original pairs as ordinary slots. The singleton slots now belong to different original pairs. For any ordinary slot \(E_t=\{x_t,y_t\}\), the following display records the selected elements in pairs \(i,j,t\). Here \(u_t\) is either element of \(E_t\), and every other ordinary pair is singly occupied: \[\begin{array}{c|ccc} &\text{pair }i&\text{pair }j&\text{pair }t\\ \hline \mathcal X_p&\varnothing&\{a_j,b_j\}&\{u_t\}\\ \mathcal X_d&\{a_i\}&\{a_j\}&\{u_t\}\\ \mathcal X_t&\{a_i\}&\{a_j,b_j\}&\varnothing\\ \text{sets counted by }v_t&\varnothing&\{a_j\}&E_t \end{array}\] Thus \(\mathcal X_p=\Omega_{ij}\) and \(\mathcal X_d=\mathcal A\), giving \[s_p=c_{ij},\quad W_p=w_{ij},\quad s_d\ge c_0/4,\quad W_d=1.\] For an ordinary hole \(t\), the class \(\mathcal X_t\) is contained in \(\Omega_{tj}\), with the choice \(a_i\) fixed at pair \(i\), so \(W_t=w_{tj}\). The sets counted by \(v_t\) lie outside \(\mathcal X\): both singleton slots are missing and \(E_t\) is doubled. In the original pairing they form the subset of \(\Omega_{it}\) with \(a_j\) selected, so \(v_t\le c_{it}\). The first two terms of the coefficient in (10) are each at most \(4/c_0\). For each ordinary slot, goodness and 3 give \[\frac{2v_t}{s_ps_dW_t} \le\frac{8c_{it}c_{tj}}{c_{ij}s_dc_0} \le\frac8{s_d}\le\frac{32}{c_0}.\] The transport subgraph again uses the unnormalized conductances in \(D\), so (29) follows. Finally, since \(\mu(\mathcal A)\ge1/4\), Jensen’s inequality on \(\mathcal A\) gives (30). ◻ Define \(\mathsf Q\) on functions on \(\Omega\) by retaining every value on \(\Omega_0\) and replacing the values on each defect class by that class’s conditional mean. It is the orthogonal projection in \(L^2(\pi)\) onto the functions that are constant on each defect class. It fixes constants and preserves expectations. This is the block-averaging operator for the partition with one singleton block for each transversal and one block for each defect class. The bound below is a partition-restricted Poincaré inequality in the sense of [11]. The inequality below controls \(\mathsf QH\), not every fluctuation of \(H\) within a defect class. This is precisely the distinction needed for the two simulation estimates in 6. Proposition 7 (Observable Poincaré inequality). For good multipliers and every \(H:\Omega\to\mathbb R\), \[ \operatorname{Var}_\pi(\mathsf QH)\le K_{\rm obs}\mathcal E(H), \qquad K_{\rm obs}=2000n^6. \tag{31}\] Proof. Bound the variance by the squared deviation from \(\overline H_0\). By [lem:transversalvariance,lem:defecttransfer], \[\begin{align*} \operatorname{Var}_\pi(\mathsf QH) &\le \pi(\Omega_0)\operatorname{Var}_\mu H +\sum_{ij}\pi(\Omega_{ij})(\overline H_{ij}-\overline H_0)^2\\ &\le \operatorname{Var}_\mu H+2C_{\rm d}\frac{D(H)}{c_0}+8\operatorname{Var}_\mu H\\ &\le (9C_{\rm p}+2C_{\rm d})\frac{D(H)}{c_0}. \end{align*}\] Using [eq:typemasses,eq:Dirichlet], the final expression is at most \[10n^4(72n^2+73n+16)\mathcal E(H) \le1610n^6\mathcal E(H)<2000n^6\mathcal E(H).\] ◻ Two consequences for simulationWe need two controls of the chain: accurate time averages of observables fixed by \(\mathsf Q\), and mixing of the trace that records successive visits to \(\Omega_0\). The averages learn type probabilities and annealing ratios; the trace supplies warm transversal starts for those averages. The proofs use finite reversible-chain facts about correlated averages, traces, and return times; see [1]. We include the arguments to retain their exact normalizations and warm-start hypotheses. Time averages from a warm startThe stationary estimate is the restricted-Poincaré empirical-average bound of Chen, Vigoda, and Yang [11]. Its dual-energy argument also has the earlier antecedent of Kipnis and Varadhan [18]. We include the finite-chain proof and extend it to a warm start by domination of trajectory laws. For probability distributions \(\nu,\pi\) on a finite set, write \(\nu\le U\pi\) to mean pointwise domination. Such a start is called \(U\)-warm. Lemma 8. Suppose the multipliers are good. If \(G=\mathsf QG\) and a trajectory \((X_t)\) of \(P\) starts with law \(\nu\le U\pi\), then for every integer \(N\ge1\), \[ \mathbb E_\nu\left[\left(\frac1N\sum_{t=0}^{N-1}G(X_t)-\mathbb E_\pi G\right)^2\right] \le\frac{2UK_{\rm obs}\operatorname{Var}_\pi G}{N}. \tag{32}\] Proof. First start in stationarity and put \(g=G-\mathbb E_\pi G\). For any \(H\), orthogonality of the projection and (31) imply \[|\langle g,H\rangle_\pi|^2 =|\langle g,\mathsf QH\rangle_\pi|^2 \le\operatorname{Var}_\pi G\,\operatorname{Var}_\pi(\mathsf QH) \le K_{\rm obs}\operatorname{Var}_\pi G\,\mathcal E(H).\] On the mean-zero subspace \(I-P\) is invertible, because \(P\) is finite and irreducible. Take \(H=(I-P)^{-1}g\) and use \(\mathcal E(H)=\langle g,H\rangle_\pi\). This gives \[ \langle g,(I-P)^{-1}g\rangle_\pi\le K_{\rm obs}\operatorname{Var}_\pi G. \tag{33}\] Reversibility makes \(P\) self-adjoint, and laziness puts its eigenvalues on the mean-zero subspace in \([0,1)\). Indeed \(P=(I+R)/2\) for a reversible stochastic matrix \(R\), whose spectrum lies in \([-1,1]\). Consequently, \[\langle g,(I-P)^{-1}g\rangle_\pi =\sum_{t\ge0}\langle g,P^tg\rangle_\pi, \qquad \langle g,P^tg\rangle_\pi\ge0.\] In the variance of the stationary average, the coefficient of each of these covariances is at most \(2/N\). This proves (32) for \(U=1\). Finally, \(\nu\le U\pi\) implies the same domination for the entire trajectory law. Applying it to the nonnegative squared error proves the general case. ◻ The trace on transversalsSet \(A=\Omega_0\). Starting from \(x\in A\), let \(\tau_A^+=\min\{t\ge1:X_t\in A\}\). The trace transition \(P_A(x,y)=\mathbb P_x(X_{\tau_A^+}=y)\) records the next visit to \(A\), including a possible visit at time one. All hitting and return times have finite expectation, since the underlying chain is finite and irreducible. For completeness, from every state there is a positive-probability path to \(A\) of bounded length; taking the minimum of these finitely many positive path probabilities gives a geometric tail in blocks of that length. Lemma 9. With good multipliers, \(P_A\) is reversible with stationary law \(\mu\), irreducible, and lazy. Its inverse spectral gap is at most \(18n^4\). In particular, for every integer \(s\ge0\), \[ \left|\frac{P_A^s(x,y)}{\mu(y)}-1\right| \le\frac{\exp(-s/(18n^4))}{\min_{z\in A}\mu(z)} \quad(x,y\in A). \tag{34}\] If a trace step begins with a law \(\nu\le U\mu\), its expected number of underlying transitions is at most \[ \frac{U}{\pi(A)}\le5Un^2. \tag{35}\] Proof. For \(h:A\to\mathbb R\), let \(H\) be its harmonic extension: \(H=h\) on \(A\) and \(H(x)=\mathbb E_x[h(X_{\tau_A})]\) off \(A\), where \(\tau_A=\min\{t\ge0:X_t\in A\}\). Conditioning on the first step gives \[(I-P)H=0\ \text{ off }A,\qquad ((I-P)H)|_A=(I-P_A)h.\] For two such extensions, symmetry of \(I-P\) implies symmetry of \(I-P_A\) in \(L^2(\mu)\), since \(\pi|_A=\pi(A)\mu\). Thus \(P_A\) is reversible and \(\mu\) is stationary. Irreducibility follows by tracing paths in the original chain, and \(P_A(x,x)\ge P(x,x)\ge1/2\). Taking the same extension in both slots gives \[ \mathcal E(H)=\pi(A)\langle h,(I-P_A)h\rangle_\mu. \tag{36}\] Because \(\pi(A)=c_0/\Lambda\), (23) gives \(D(H)/c_0=2n^2\mathcal E(H)/\pi(A)\). Applying 5 to \(H\) therefore yields \[\operatorname{Var}_\mu h\le2n^2C_{\rm p}\langle h,(I-P_A)h\rangle_\mu, \qquad 2n^2C_{\rm p}\le18n^4.\] This proves the spectral-gap bound. Laziness makes every nonconstant trace eigenvalue nonnegative. Applying the centered operator norm bound to the point densities at \(x,y\), whose centered \(L^2(\mu)\) norms are at most \(\mu(x)^{-1/2},\mu(y)^{-1/2}\), gives \[\left|\frac{P_A^s(x,y)}{\mu(y)}-1\right| \le\frac{(1-1/(18n^4))^s}{\sqrt{\mu(x)\mu(y)}},\] which implies (34). To prove the cost statement, start a return excursion with distribution \(\mu\) and let \(v(z)\) be the expected number of visits to \(z\) at times \(0,\ldots,\tau_A^+-1\). Multiplying \(v\) by \(P\) shifts these expected occupations to times \(1,\ldots,\tau_A^+\). The initial and final laws are both \(\mu\), so \(vP=v\). By uniqueness of the stationary law, \(v\) is a scalar multiple of \(\pi\). Since \(v|_A=\mu\), that scalar is \(1/\pi(A)\). Summing over \(z\) proves \(\mathbb E_\mu\tau_A^+=1/\pi(A)\). Domination of the starting law gives the factor \(U\), and (21) finishes (35). ◻ Annealing and learning the multipliersThe initial transversal weight is known at \(q=1\). We estimate its successive ratios as \(q\) decreases, while learning multipliers that keep every type sufficiently frequent. The trace supplies a fresh warm start for each estimation phase, and the observable variance bound controls the resulting averages. The frequency-ratio updates and balancing of defect totals adapt the interpolation strategy of Jerrum, Sinclair, and Vigoda [16]; the warm restarts below use the trace and observable estimates proved here. We first specify a run with constant success probability using exact rational random choices. The next section gives a bounded-bit implementation and amplification. The feasibility test in 2 is performed before these runs. Parameters and the scheduleLet \(b\) be the least nonnegative integer with \(2^{-b}\le\epsilon/10\), and set \[ \rho=1-\frac1{2n},\qquad L=2n(n+b),\qquad q_j=\rho^j\ (0\le j\le L),\qquad \eta=\frac{\epsilon}{32(L+1)}. \tag{37}\] The restart and estimation routines use three integer parameters: \[ \begin{split} \tau&=20n^4\bigl(n(L+1)+2\bigr),\\ B_{\rm restart}&=2000(L+1)^2n^2\tau,\\ N_{\rm av}&=\left\lceil\frac{10^{10}(L+1)n^{14}}{\eta^2}\right\rceil. \end{split} \tag{38}\] Here \(\tau\) is the number of trace transitions at each restart stage, \(B_{\rm restart}\) caps the total underlying transition attempts in one restart, and \(N_{\rm av}\) is the number of observations in one estimation phase. We make no attempt to optimize these polynomial bounds. Bernoulli’s inequality and \(1-x\le e^{-x}\) give \[ \rho^n\ge\frac12,\qquad \rho^{2n}\le e^{-1}<\frac12,\qquad 2^{-L}\le q_L\le2^{-(n+b)}. \tag{39}\] For every state and every \(j<L\), \[ \frac12\le\frac{f_{q_{j+1}}(S)}{f_{q_j}(S)} =\rho^{d(S)}\le1. \tag{40}\] The same inequalities hold for each ratio \(c_T(q_{j+1})/c_T(q_j)\). Thus the ideal multiplier \(w^*_{ij}=c_0/c_{ij}\) changes by a factor between \(1/2\) and \(2\) per phase. Write \(\mu_j\) for the transversal law at \(q_j\). Equation (40) also gives \[ \mu_j\le2\mu_{j+1}. \tag{41}\] One runAt \(q_0=1\), \(\mu_0\) is uniform on the \(2^n\) transversals, \(c_0=2^n\), and \(c_{ij}=2^{n-2}\) whenever a defect type exists. Initialize \(w^{(0)}_{ij}=4\). Store every subsequent phase’s multipliers as they are learned. The observations used to learn these multipliers also reveal the preceding trajectory’s endpoint. After conditioning on that history, the endpoint need not satisfy the polynomial warm-start bound needed below. Each phase therefore generates a fresh starting transversal from the known law \(\mu_0\), through the stored parameter levels and with independent randomness. For \(j=0,\ldots,L-1\), perform the following steps. Any abort mentioned below returns zero from the run.
If every phase completes, output \[ \widehat Z=2^n\prod_{j=0}^{L-1}\widehat R_j. \tag{45}\] Warm restarts and estimation errorCondition on any complete previous phase history in which all stored multipliers are good at their respective parameters. Under this conditioning the fresh restart uses fixed kernels and independent randomness, starting from the known law \(\mu_0\). Analyze the uncapped restart and its subsequent observations; the capped process agrees whenever the restart finishes within its cap. Uniformly over all phases and all transversals, (39) gives \[ \mu_j(S)\ge\frac{q_L^n}{2^n}\ge2^{-n(L+1)}. \tag{46}\] By 9 and (38), after \(\tau\) trace transitions the density relative to the current \(\mu_a\) lies between \(1/2\) and \(3/2\), from any initial distribution. Indeed, \[\exp\bigl(-\tau/(18n^4)\bigr)\,2^{n(L+1)}\le\tfrac12.\] At the start of each stage the law is at most \(4\mu_a\): at the previous parameter it is at most twice that parameter’s transversal law, and (41) costs at most a further factor of two. For the first stage the starting law is exactly \(\mu_0\). Pointwise domination by \(4\mu_a\) persists through the stage because \(\mu_a\) is stationary for its trace. Thus (35), applied at each trace step, implies \[ \mathbb E[\text{underlying transitions in the restart}] \le20n^2L\tau. \tag{47}\] Markov’s inequality yields \[ \mathbb P[\text{restart exceeds }B_{\rm restart}] \le\frac{L}{100(L+1)^2}\le\frac1{32(L+1)}. \tag{48}\] The endpoint law of the uncapped restart is at most \(2\mu_j\), including the case \(j=0\). Since \(\pi(\Omega_0)\ge1/(5n^2)\), it is at most \(10n^2\pi\), where \(\pi\) is the enlarged chain’s stationary law at the current parameters. Every type indicator and \(G_j\) belongs to the range of \(\mathsf Q\) and takes values in \([0,1]\). Their stationary means are \[ p_T=\pi(\Omega_T),\qquad u=p_0R_j,\qquad R_j=\frac{c_0(q_{j+1})}{c_0(q_j)}. \tag{49}\] All these means are at least \(1/(20n^2)\), by [eq:typemasses,eq:stepweight]. 8 bounds the mean squared error of each empirical average around its stationary mean by \[ \frac{40000n^8}{N_{\rm av}}. \tag{50}\] There are \(n(n-1)+2\le2n^2\) observables. Applying Markov’s inequality to each squared error and taking a union bound gives \[\begin{align*} \mathbb P\bigl[\text{some relative error exceeds }\eta\bigr] &\le 2n^2\frac{40000n^8}{N_{\rm av}} \frac{400n^4}{\eta^2}\\ &\le\frac{0.0032}{L+1}\le\frac1{32(L+1)}. \tag{51}\end{align*}\] Both error probabilities were bounded in the uncapped experiment. Their union contains failure of the actual phase, since the two simulations agree whenever the restart finishes within its cap. When neither event occurs, all empirical type probabilities are positive and no zero-count abort occurs. Induction on learned weightsOn a phase with all relative errors at most \(\eta\), the exact identity \[w^{(j)}_{ij}\frac{p_0}{p_{ij}}=\frac{c_0(q_j)}{c_{ij}(q_j)}\] shows that (44) estimates the current ideal multiplier within factors \((1-\eta)/(1+\eta)\) and its reciprocal. These factors lie between \(1/2\) and \(2\). The ideal multiplier changes by at most a factor of two at the next parameter, so the new multipliers are good for phase \(j+1\). Initialization is ideal. Conditional on any previously successful history, [eq:restartfailure,eq:estimationfailure] bound the next phase’s failure probability by \(1/[16(L+1)]\). Induction and a union bound over all \(L\) phases therefore give \[ \mathbb P[\text{some restart abort or inaccurate phase}]\le\frac1{16}. \tag{52}\] Accuracy of the productOn the complementary event in (52), \[ \frac{1-\eta}{1+\eta}\le\frac{\widehat R_j}{R_j} \le\frac{1+\eta}{1-\eta}. \tag{53}\] Since \(\eta<1/2\) and \(\log((1+\eta)/(1-\eta))\le4\eta\), the telescoping product satisfies \[e^{-4L\eta}\le\frac{\widehat Z}{c_0(q_L)}\le e^{4L\eta}.\] Here \(c_0(q_0)=2^n\). Equation (37) gives \(4L\eta\le\epsilon/8\), and for \(0<\epsilon<1\), \[ (1-\epsilon/4)c_0(q_L)\le\widehat Z \le(1+\epsilon/4)c_0(q_L). \tag{54}\] Every transversal basis of \(K\) has weight one; every other transversal has weight at most \(q_L\). Therefore, writing \(Z=Z(M_1,M_2)\), \[ Z\le c_0(q_L)\le Z+2^nq_L \le Z+\epsilon/10\le(1+\epsilon/10)Z, \tag{55}\] where the final inequality uses the feasibility test, \(Z\ge1\). Combining [eq:productaccuracy,eq:contamination] gives \[(1-\epsilon)Z\le\widehat Z\le(1+\epsilon)Z.\] Thus the run using exact random choices has success probability at least \(15/16\). Oracle implementation, bit bounds, and amplificationWe now implement the run with independent fair bits and bound all work on every execution, including those with inaccurate estimates or aborts. States and oracle weightsRepresent a state by its \(2n\)-bit indicator. Its occupancy pattern, a proposed exchange, and membership in \(\Omega\) can be computed in polynomial time. For \(S\subseteq V\), let \(S_x,S_y\subseteq[n]\) be its positions in the two copies. The required rank is \[ \operatorname{rk}_K(S)=\operatorname{rk}_{M_1}(S_x)+|S_y|-r +\operatorname{rk}_{M_2}([n]\setminus S_y). \tag{56}\] Both original ranks are computed greedily. This takes at most \(2n\) original independence queries, with polynomial overhead for constructing their \(n\)-bit indicators. Consequently no oracle other than the two given independence oracles is needed. Sizes of the rational numbersThe integer \(b\) in (37) is \(O(\ell)\) and can be found using shifts and binary comparisons. Thus \(L\) is polynomial in \(n,\ell\). The integers \(\tau,B_{\rm restart},N_{\rm av}\) are polynomial in \(n,\ell,\epsilon^{-1}\), since \(\eta^{-1}=32(L+1)\epsilon^{-1}\). We may store unreduced numerator–denominator pairs throughout. If \(C_T\) is a type count among the \(N_{\rm av}\) observations, then the multiplier update is multiplication by \(C_0/C_{ij}\). A zero denominator causes an abort before division. After at most \(L\) phases, all multiplier numerators and denominators have bit length \[ O\bigl(1+L\log(N_{\rm av}+1)\bigr). \tag{57}\] This bound holds even when the empirical estimates are inaccurate. For \(0\le d\le n\), the observable \(\rho^d\) has common denominator \((2n)^n\) and integer numerator \((2n-1)^d(2n)^{n-d}\). If \(X_t\) denotes the \(t\)th observation in phase \(j\) and \(C_0>0\) counts the transversals among those observations, the exact implementation is \[ A_j=\sum_{\substack{0\le t<N_{\rm av}\\X_t\in\Omega_0}} (2n-1)^{d(X_t)}(2n)^{n-d(X_t)}, \qquad \widehat R_j=\frac{A_j}{(2n)^nC_0}. \tag{58}\] The accumulator has bit length \(O(\log(N_{\rm av}+1)+n\log(2n))\). The rational product (45) has bit length \[ O\bigl(n+L\log(N_{\rm av}+1)+Ln\log(2n)\bigr). \tag{59}\] Finally, \(q_j^d=((2n-1)/(2n))^{jd}\) has numerator and denominator bit length \(O(1+Ln\log(2n))\). Together with (57), this bounds the sizes of state weights, acceptance fractions, and all comparisons by a fixed polynomial. Each state weight is formed directly from its rank deficiency, the stored multiplier of its type, and \(q_j^{d(S)}\). Integer arithmetic on these lengths, including multiplication, division, and comparison, takes polynomial bit operations. Exact rational choices with bounded trialsTo draw uniformly from \(\{0,\ldots,v-1\}\), use \(\lceil\log_2v\rceil\) unbiased bits and reject values at least \(v\). For \(v=1\), return zero without drawing bits. With unrestricted trials the distribution is exactly uniform, and every trial succeeds with probability at least \(1/2\). A rational acceptance probability \(a/v\) is implemented by checking whether this uniform integer is less than \(a\). The denominators have polynomial bit length by the preceding subsection. With the restart attempt caps, a run uses at most \[ M=3L(B_{\rm restart}+N_{\rm av}) \tag{60}\] uniform-integer calls: two for the proposed exchange and one for its acceptance, per underlying transition. Laziness and initial uniform transversals use fair bits directly. Choose the least positive integer \(D_{\rm bits}\) satisfying \[ M2^{-D_{\rm bits}}\le1/32. \tag{61}\] Allow at most \(D_{\rm bits}\) trials in each uniform-integer call; if all fail, abort the run and return zero. The cap is \(O(1+\log M)\). Couple this procedure with the unrestricted-trial one using the same random bits up to an abort. Conditional on the previous history, a call exceeds its cap with probability at most \(2^{-D_{\rm bits}}\), even if its denominator depends on that history. A union bound over (60) therefore bounds the coupling failure probability by \(1/32\). Combining this with (52), the bounded run succeeds with probability at least \[ 1-\frac1{16}-\frac1{32}=\frac{29}{32}>\frac34. \tag{62}\] Every execution has at most \(L(B_{\rm restart}+N_{\rm av})\) underlying transition attempts, including any attempt interrupted by a bit-cap abort. If \(h_{\max}\) is the polynomial bound on the bit lengths of uniform-integer denominators established above, the total number of random bits is at most \[nL+L(B_{\rm restart}+N_{\rm av})+MD_{\rm bits}h_{\max}.\] The first two terms cover initial transversals and laziness. Together with (56) and the rational size bounds, this proves polynomial oracle and bit-operation bounds for a run. In particular, exceptional histories affect success probability but cannot cause an unbounded execution. Amplification and completion of the proofLet \(b_\delta\) be the least nonnegative integer with \(2^{-b_\delta}\le\delta\), and perform \(J=10b_\delta+1\) independent bounded runs after the feasibility pretest. Return their rational median. The number \(J\) is odd and is \(O(1+\log\delta^{-1})\). For each run let \(X\) be its failure indicator relative to the desired interval \([(1-\epsilon)Z,(1+\epsilon)Z]\). By (62), \(\mathbb E[2^X]\le5/4\). Independence and Markov’s inequality imply \[\mathbb P[\text{at least half the runs fail}] \le\left(\frac{5}{4\sqrt2}\right)^J \le2^{-b_\delta}\le\delta,\] using \((5/(4\sqrt2))^{10}<1/2\). If a strict majority of estimates lie in the desired interval, so does their median. Computing \(b_\delta\) and comparing rational estimates costs polynomial bit operations, including the dependence on \(\ell\). For an infeasible input the deterministic pretest returns zero. If \(n=0\), the unique common basis is empty and the initial output is one. For all remaining ranks, including \(r=0\) and \(r=n\), the preceding argument applies. Every output is a nonnegative rational, and all complexity bounds are uniform over the two promised independence oracles. This proves 1. Counting and sampling common independent setsThe equal-rank common-bases theorem also gives counting and sampling algorithms for common independent sets when the input ranks differ. Truncation reduces prescribed-cardinality counting to common bases; self-reduction then supplies sampling. Corollary 10 (Common independent sets). Let \(M_1,M_2\) be arbitrary matroids on an explicitly enumerated ground set \([n]\), supplied by fixed exact independence oracles with \(n\)-bit subset queries. Their ranks may differ. For an integer \(k\), let \(\mathcal C_k\) consist of the \(k\)-element subsets of \([n]\) independent in both matroids, and put \[\mathcal C=\bigcup_{j=0}^n\mathcal C_j,\qquad h=\max_{I\in\mathcal C}|I|,\qquad \mathcal C_{\max}=\mathcal C_h.\] The maximum \(h\) is well defined because \(\varnothing\in\mathcal C\). Each family \(\mathcal F\in\{\mathcal C_k,\mathcal C,\mathcal C_{\max}\}\) has the following algorithms.
Here \(\ell\) is the binary encoding length of the numerical inputs to the algorithm in question, including \(k\) only for \(\mathcal C_k\). Both algorithms use only the two given independence oracles and independent unbiased random bits. The counting-to-generation principle for self-reducible families is classical [17]. The direct argument below records the exact independence-oracle interface, the total-variation error, and the work bound on every execution. Proof of Corollary 10. Counting by truncation. Use the deterministic matroid-intersection algorithm [20], already invoked in 2, to find the maximum common independent-set size \(h\). Its input permits different ranks and requires only the promised matroid axioms, a common explicit ground set, and exact independence oracles. If \(k<0\) or \(k>h\), then \(\mathcal C_k\) is empty, so return \(0\) for its count. If \(k=0\), return \(1\). For \(0<k\le h\), define the truncation \(T_k(M_i)\) by declaring \(J\) independent exactly when it is independent in \(M_i\) and \(|J|\le k\). Both truncations have rank exactly \(k\): a common independent set of size \(h\) contains an independent \(k\)-set in each matroid. Their common bases are therefore precisely \(\mathcal C_k\). A truncation query uses at most one original independence query and a cardinality check, so 1 applies with the required oracle and bit bounds even if the original ranks differ. For \(\mathcal C\), estimate each \(|\mathcal C_j|\), \(0\le j\le h\), with relative error \(\epsilon\) and failure probability \(\delta/(h+1)\), and add the nonnegative rational estimates. With probability at least \(1-\delta\), all estimates satisfy their relative bounds simultaneously. Adding those bounds gives \[(1-\epsilon)|\mathcal C| \le\sum_{j=0}^h\widehat N_j \le(1+\epsilon)|\mathcal C|.\] There are at most \(n+1\) terms. For \(\mathcal C_{\max}\), use the prescribed-cardinality procedure at \(k=h\). The families \(\mathcal C\) and \(\mathcal C_{\max}\) are always nonempty; when \(h=0\), both consist only of the empty set. The feasibility tests thus handle every zero-count case exactly. Since \(\log((h+1)/\delta)=O(\log(n+1)+\log\delta^{-1})\), the confidence allocation preserves the stated fully polynomial counting bound. Exact feasibility during self-reduction. For sampling, first perform the same exact emptiness test, returning \(\bot\) if the requested family is empty. If \(n=0\), return \(\varnothing\). Otherwise initialize \(A=D=\varnothing\). Maintain disjoint sets \(A,D\) of included and excluded elements, with \(A\) common independent and at least one requested set consistent with these choices, and let \(R=[n]\setminus(A\cup D)\) be the remaining ground set. Define \(N_i\) on \(R\) by declaring, for \(J\subseteq R\), \[ J\text{ independent in }N_i \quad\Longleftrightarrow\quad A\cup J\text{ independent in }M_i. \tag{63}\] The empty set is independent because \(A\) is, and heredity and augmentation follow from those of \(M_i\). Thus \(N_i\) is a matroid, namely the restriction to \(R\) of the contraction \(M_i/A\). After relabeling \(R\), an exact query to either residual minor uses one original query and polynomial work to construct its \(n\)-bit indicator. If \(R=\varnothing\), return \(A\). Otherwise let \(e\) be the least element of \(R\). The exclusion branch has included set \(A\) and excluded set \(D\cup\{e\}\). Before constructing the inclusion branch, test whether \(A\cup\{e\}\) is independent in both original matroids; if not, that branch is empty. Otherwise that branch has included set \(A\cup\{e\}\) and excluded set \(D\), and (63) again supplies valid minor oracles. The remaining ground set in either branch is \(R\setminus\{e\}\). For a prescribed original cardinality \(t\), including the case \(t=h\) for maximum-cardinality sampling, the branch with decision \(b\in\{0,1\}\) has as many completions as the residual pair has common independent sets of size \(t-|A|-b\). The prescribed-cardinality pretest above decides exactly whether this count is zero; the original target \(t\) stays fixed throughout the recursion. For unrestricted cardinality, the branch count is the all-cardinalities count of the residual pair; it is positive whenever the branch’s included set is common independent. These descriptions partition the current feasible completions into two smaller instances, at least one of which is nonempty. Branch probabilities and sampling error. Let \(a_0,a_1\) be their true counts. For comparison, the ideal recursion with access to these counts chooses the inclusion branch with probability \(p=a_1/(a_0+a_1)\); induction on \(|R|\) shows that it is uniform on the requested family. The actual recursion follows the unique feasible branch deterministically when only one exists. When both are feasible, obtain fresh estimates \(\widehat a_0,\widehat a_1\) from the appropriate counter, each with relative tolerance and failure probability \[\alpha=\frac{\theta}{4n},\qquad \beta=\frac{\theta}{8n}.\] If \(\widehat a_0+\widehat a_1=0\), set \(\widehat p=0\); this selects a known-feasible branch. Otherwise set \(\widehat p=\widehat a_1/(\widehat a_0+\widehat a_1)\). This rule does not mistake a zero estimate on an inaccurate run for proof that a branch is empty. Let \(s\) be the least nonnegative integer with \(2^{-s}\le\theta/(4n)\), and put \[p_s=2^{-s}\lfloor 2^s\widehat p\rfloor.\] Use exactly \(s\) fresh unbiased bits to obtain a uniform integer in \(\{0,\ldots,2^s-1\}\) and choose inclusion when it is less than \(2^sp_s\). This implements \(p_s\) with \(|p_s-\widehat p|<2^{-s}\), without an unbounded rejection procedure. When both estimates are accurate, write \(\widehat a_b=a_b(1+u_b)\) with \(|u_b|\le\alpha\). Since \(a_0,a_1>0\), \[|\widehat p-p| =\frac{a_0a_1|u_1-u_0|} {(a_0+a_1)\bigl(a_0(1+u_0)+a_1(1+u_1)\bigr)} \le\frac{\alpha}{2(1-\alpha)} \le\alpha,\] where the last inequality uses \(\alpha<1/2\). Conditional on every shared history of the ideal and actual recursions, fresh randomness makes the probability that either estimate is inaccurate at most \(2\beta\). Couple their next decisions; the conditional probability that they separate is at most \[\alpha+2\beta+2^{-s}\le\frac{3\theta}{4n}.\] This also holds at a forced decision, where the probability is zero. A sequential coupling over at most \(n\) decisions now gives \[d_{\rm TV}\bigl(\mathcal L(S),\operatorname{Unif}(\mathcal F)\bigr) \le n\bigl(\alpha+2\beta+2^{-s}\bigr) \le\frac{3\theta}{4}<\theta.\] The exact branch tests keep every output in the requested family, including on executions with inaccurate estimates. Finally, each sampling step uses at most two counter calls and polynomial exact matroid-intersection work. An all-cardinalities counter uses at most \(n+1\) common-bases calls. The derived parameters satisfy \(\alpha^{-1}=4n/\theta\), \(\log\beta^{-1}=O(1+\log n+\log\theta^{-1})\), and \(s=O(1+\log n+\log\theta^{-1})\). Their binary encodings have polynomial length, and \(s\) can be found by shifts and rational comparisons. The every-execution bound in 1 bounds the lengths of the returned rationals; summing at most \(n+1\) such rationals, forming \(\widehat p\), and computing its dyadic rounding therefore take polynomial bit operations. Together with (63), these observations give the asserted oracle and bit bounds on every execution. ◻
|
| ||||||||
|