On the number of matroids compared to the number of sparse paving matroids (Q491548): Difference between revisions

Summary: It has been conjectured that sparse paving matroids will eventually predominate in any asymptotic enumeration of matroids, i.e. that \(\lim_{n\to\infty} s_n/m_n = 1\), where \(m_n\) denotes the number of matroids on \(n\) elements, and \(s_n\) the number of sparse paving matroids. In this paper, we show that \[ \lim_{n\to \infty}\frac{\log s_n}{\log m_n}=1. \] We prove this by arguing that each matroid on \(n\) 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 \(n\) elements. As a consequence of our result, we find that for all \(\beta > \displaystyle{\sqrt{\frac{\ln 2}{2}}} = 0.5887\cdots\), asymptotically almost all matroids on \(n\) elements have rank in the range \(n/2 \pm \beta\sqrt{n}\).