The Setting
Take two matroids and on the same ground set of elements, and ask how many subsets of are a basis of both. The perfect matchings of a bipartite graph with no isolated vertex are an instance: they are the common bases of two partition matroids on its edges, in the first of which a set of edges is independent when it meets each left vertex at most once, in the second when it meets each right vertex at most once.
The matroids are not listed. An algorithm sees them only through independence queries, and from the answers it is to estimate the number of common bases within a prescribed relative error , as a fully polynomial randomized approximation scheme for the count does. The definitions below fix that input and that target.
The Definition
Subsets of are queried as bit vectors: with , a vector marks the set . For a matroid with ground set , is its family of independent sets.
Definition 1. Let and be matroids with ground set .
An independence oracle on is a function that assigns a bit to each pair of a selector and a bit vector : (1)✦
An independence oracle on is exact for and when, for every , (2)✦
The number of common bases of and is (3)✦
For rational numbers and and a natural number , the estimate has relative accuracy for when (4)✦
In the paper, the result reads: and are matroids of the same rank on , given by exact independence oracles that answer -bit subset queries, and , where is the set of bases of .
What Is Checked
The definitions are stated over two matroids and with ground set , an independence oracle on as in (1), and, in (4), rational numbers and with a natural number .