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.