On the number of bases of almost all matroids

Abstract

For a matroid $M$ of rank $r$ on $n$ elements, let $b(M)$ denote the fraction of bases of $M$ among the subsets of the ground set with cardinality $r$. We show that $$\Omega (1/n)\le 1-b(M)\le O(\log (n{)}^3/n)\text{ as }n\to \infty$$ for asymptotically almost all matroids $M$ on $n$ elements. We derive that asymptotically almost all matroids on $n$ elements (1) have a $U_{k,2k}$-minor, whenever $k\le O(\log (n))$, (2) have girth $\ge \Omega (\log (n))$, (3) have Tutte connectivity $\ge \Omega (\sqrt{\log (n)})$, and (4) do not arise as the truncation of another matroid. Our argument is based on a refined method for writing compressed descriptions of any given matroid, which allows bounding the number of matroids in a class relative to the number of sparse paving matroids.

arXiv comment18 pages, 2 figures