On the number of matroids (Q313452): Difference between revisions

Let \(m_{n}\) denote the number of matroids on \(n\) elements. The best known lower bound on \(m_{n}\) is due to \textit{D. E. Knuth} [J. Comb. Theory, Ser. A 16, 398--400 (1974; Zbl 0278.05010)] who showed that \(\log \log m_{n}\) is at least \(n-\frac{3}{2}\log n-O(1)\). On the other hand, \textit{M. J. Piff} [J. Comb. Theory, Ser. B 14, 241--245 (1973; Zbl 0258.05026)] showed that \(\log \log m_{n} \leq n-\log n + \log \log n + O(1)\), and it has been conjectured since that the right answer is perhaps closer to Knuth's bound. The authors show that this is indeed the case, and prove an upper bound on \(\log \log m_{n}\) that is within an additive 1+o(1) term of Knuth's lower bound, namely: \(\log \log m_{n} \leq n- \frac{3}{2}\log n +\frac{1}{2}\log \frac{2}{\pi} +1+O(1)\). Their proof is based on using some structural properties of non-bases in a matroid together with some properties of stable sets in the Johnson graph to give a compressed representation of matroids.