On the number of matroids

Abstract

We consider the problem of determining $m_n$, the number of matroids on $n$ elements. The best known lower bound on $m_n$ is due to Knuth (1974) who showed that $\log \log m_n$ is at least $n-3/2\log n-1$. On the other hand, Piff (1973) showed that $\log \log m_n\le 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. We 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. Our proof is based on using some structural properties of non-bases in a matroid together with some properties of independent sets in the Johnson graph to give a compressed representation of matroids.

Final version, 17 pages