A new bound on the number of matroids
Jorn van der Pol
(joint work with Nikhil Bansal and Rudi Pendavingh)
Matroids are discrete structures that appear naturally throughout discrete
mathematics. A fundamental question in matroid theory is: how many matroids can
there be on a ground set of size n? Call this number m_n. The best known bounds
are by Piff (1973) and Knuth (1974), who showed that
n - (3/2) log n + O(1) <= log log m_n <= n - log n + O(1).
In this talk, we describe and then exploit the intimate relation between
matroids and the so-called Johnson graph. Adapting a method recently used by
Alon, Balogh, Morris and Samotij (2012), we are able to bound the number of
stable sets in the Johnson graph (based on the smallest value of the adjacency
matrix). This immediately bounds the number of matroids that are called sparse
paving.
We then introduce the notion of a flat cover. Flat covers allow us to produce a
short description of a matroid, and when we combine it with the counting method
from above, this produces even sharper results. Using this method, we prove that
log log m_n <= n - (3/2) log n + O(1),
thus substantially improving the current best upper bound.