Approximating the Number of Bases for Almost All Matroids
Brian D. Cloteaux
We define a class of matroids A for which a fully polynomial randomized approximation scheme (fpras) exists for counting the number of bases of the matroids. We then show that as the number of elements in a matroid increases, the probability that a matroid belongs to A goes to 1. We thus provide a fpras for counting the number of bases that applies to almost all matroids.
Approximating the Number of Bases for Almost All Matroids, Congressus Numerantium, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=900881
(Accessed December 3, 2023)