The Setting
Let and be matroids on , each with ground set all of , and let be the number of their common bases. The goal is a fully polynomial randomized approximation scheme (FPRAS) for , given an independence oracle for each matroid. The paired-ground-set reduction works on , two copies of , in which the copies and of each form a pair.
A transversal of the pairs is a set containing exactly one element of each pair. Exchanging one element of a transversal for another, as an exchange walk does, gives a transversal again or a set in which one pair has neither of its elements and another has both. Sets of are weighted by a power of a real parameter set by their rank in a matroid on .
The library states the item for any finite set and list of pairs of its elements, and for any real function on the subsets of in place of the weights.
Pairs and Slot Totals
A pair of is empty in a set if neither nor lies in ✦, full in if both do✦, and single in if one of them lies in and the other does not.✦
The multiaffine polynomial of a real function on the subsets of is the polynomial (1) in variables , , whose coefficient function is . For a vector , the derivative in direction is , and the direction of a pair is the indicator vector of .✦ For and a polynomial , is the coefficient of in .
The slot total of over a list of pairs at a set is the coefficient of in the derivative of along the directions of all pairs of : (2)✦ The slot total of over all of at the empty set is .
For pairs and of , the defect total of type at is the slot total over the list with and removed, taken at with both elements of added; its value at the empty set is : (3)✦
The Claim
Definition 1. Let be a matroid with rank function , let be a natural number and let be a real number. The rank weight of a set is the real number (4)✦ A plain state of is a set in which every pair of is single; is the set of plain states.✦ For distinct pairs and of , a defect state of type is a set in which is empty, is full and every other pair of is single; is the set of defect states of type .✦ A chain state of is a plain state or a defect state of some type, and the set of chain states is (5)✦ the union running over all ordered choices of distinct and in . If the pairs of are disjoint two-element sets whose union is , then for every real function on the subsets of and all distinct pairs and of , (6)✦ (7)✦
In the paper, the result reads: with , is the set of transversals of the pairs, is the set of -element sets with pair empty, pair full and every other pair single, and for each of these sets , where is the page’s and its .
What Is Checked
The definitions (4) and (5) and the identities (6) and (7) are stated over the rank function of a matroid, a list of pairs of elements of a finite set , the ways a pair can be empty, single or full in a set, the derivatives of the multiaffine polynomial (1) along the indicator vectors of pairs, and the hypothesis that the pairs are disjoint two-element sets whose union is .