t has been conjectured that sparse paving matroids will eventually predominate in any asymptotic enumeration of matroids, i.e. that limn→∞sn/mn=1limn→∞sn/mn=1, where mnmn denotes the number of matroids on nn elements, and snsn the number of sparse paving matroids. In this paper, we show that limn→∞logsnlogmn=1. limn→∞logsnlogmn=1. We prove this by arguing that each matroid on nn elements has a faithful description consisting of a stable set of a Johnson graph together with a (by comparison) vanishing amount of other information, and using that stable sets in these Johnson graphs correspond one-to-one to sparse paving matroids on nn elements. As a consequence of our result, we find that for all β>ln22−−−−√=0.5887⋯β>ln22=0.5887⋯, asymptotically almost all matroids on nn elements have rank in the range n/2±βn−−√n/2±βn.
|Number of pages||17|
|Journal||The Electronic Journal of Combinatorics|
|Publication status||Published - 15 Jun 2015|
- Asymptotic enumeration
- Matroid theory